Nonserial dynamic programming formulations of satisfiability
From MaRDI portal
Publication:1099093
DOI10.1016/0020-0190(88)90221-9zbMath0637.90100MaRDI QIDQ1099093
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(88)90221-9
satisfiability; bandwidth-k interaction graphs; nonserial dynamic programming; planar separator theorem
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
90C27: Combinatorial optimization
90C39: Dynamic programming
Cites Work
- An application of the planar separator theorem to counting problems
- Bandwidth contrained NP-complete problems
- Contribution to nonserial dynamic programming
- Allocating programs containing branches and loops within a multiple processor system
- Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
- Applications of a Planar Separator Theorem
- Planar Formulae and Their Uses
- Dynamic Programming is Optimal for Nonserial Optimization Problems
- Linear-time computation of optimal subgraphs of decomposable graphs