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

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)

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)