Nonserial dynamic programming formulations of satisfiability

DOI10.1016/0020-0190(88)90221-9MaRDI QIDQ1099093zbMATH OpenOpenAlexFDO

Authors 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

bandwidth-k interaction graphsnonserial dynamic programmingplanar separator theoremsatisfiability

Mathematics Subject Classification ID

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

Review text

Two nonserial dynamic programming formulations of satisfiability are presented: one mapping planar formulas into nonserial problems with planar interaction graphs, the other mapping bandwidth-k formulas into nonserial problems with bandwidth-k interaction graphs.

Recommendations

• scientific article; zbMATH DE number 1336257
• scientific article; zbMATH DE number 1538056
• scientific article; zbMATH DE number 956858
• scientific article; zbMATH DE number 4039349
• Solving propositional satisfiability problems

Cites work

• Allocating programs containing branches and loops within a multiple processor system
• An application of the planar separator theorem to counting problems
• Applications of a Planar Separator Theorem
• Bandwidth contrained NP-complete problems
• Contribution to nonserial dynamic programming
• Dynamic Programming is Optimal for Nonserial Optimization Problems
• Linear-time computation of optimal subgraphs of decomposable graphs
• Planar Formulae and Their Uses
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems

Cited in

(1)

• A satisfiability formulation of problems on level graphs

This page was built for publication: Nonserial dynamic programming formulations of satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099093)