A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems

DOI10.1016/j.camwa.2009.06.008zbMath1189.90186DBLPjournals/cma/LazarevW09OpenAlexW2131992008WikidataQ57633882 ScholiaQ57633882MaRDI QIDQ980008

Alexander A. Lazarev, Frank Werner

Publication date: 28 June 2010

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.camwa.2009.06.008

zbMATH Keywords

dynamic programminggraphical algorithmexact algorithmKnapsack problempartition problem

Mathematics Subject Classification ID

Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of algorithms (68W01)

Related Items (8)

Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering ⋮ Algorithms for some maximization scheduling problems on a single machine ⋮ A graphical approach to solve an investment optimization problem ⋮ On the best choice of a branching variable in the subset sum problem ⋮ A new effective dynamic program for an investment optimization problem ⋮ Graphical method to solve combinatorial optimization problems ⋮ Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one ⋮ A note on a single machine scheduling problem with generalized total tardiness objective function

Cites Work

• Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems