Nonserial dynamic programming formulations of satisfiability

DOI10.1016/0020-0190(88)90221-9zbMath0637.90100OpenAlexW2018339184MaRDI QIDQ1099093

David Fernández Baca

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

zbMATH Keywords

satisfiabilitybandwidth-k interaction graphsnonserial dynamic programmingplanar separator theorem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39)

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