A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time

DOI10.1007/978-3-319-89920-6_40zbMath1397.90423OpenAlexW2804967896MaRDI QIDQ4685763

Carolin Rehs, Frank Gurski

Publication date: 9 October 2018

Published in: Operations Research Proceedings (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-89920-6_40

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Counting and enumerating independent sets with applications to combinatorial optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Directed path-width and directed tree-width of directed co-graphs
• Threshold graphs and related topics
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Ond-threshold graphs andd-dimensional bin packing
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• The Complexity of the Partial Order Dimension Problem