Computational complexity of the original and extended diophantine Frobenius problem

DOI10.1134/S1990478917030048zbMath1399.11084OpenAlexW2752298195MaRDI QIDQ5374005

V. M. Fomichev

Publication date: 6 April 2018

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478917030048

zbMATH Keywords

computational complexityFrobenius numberadditive semigroupprimitive set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer solution of Diophantine equations (11Y50) Linear Diophantine equations (11D04) The Frobenius problem (11D07)

Related Items (2)

Primitivity and Local Primitivity of Digraphs and Nonnegative Matrices ⋮ On improved universal estimation of exponents of digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric proof of Rødseth's formula for Frobenius numbers
• A graph-theoretic algorithm for the solution of a linear diophantine problem of Frobenius
• On a linear diophantine problem of Frobenius: an improved algorithm
• On formulas for the Frobenius number of a numerical semigroup.
• A Minimal-Path Algorithm for the "Money Changing Problem"
• Efficient Algorithms for Shortest Paths in Sparse Networks
• The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments
• Computing and Combinatorics
• On a Problem of Partitions

This page was built for publication: Computational complexity of the original and extended diophantine Frobenius problem