Nonserial dynamic programming formulations of satisfiability

DOI10.1016/0020-0190(88)90221-9zbMATH Open0637.90100OpenAlexW2018339184MaRDI QIDQ1099093FDOQ1099093

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

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

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

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