Boundary properties of the satisfiability problems

DOI10.1016/j.ipl.2013.01.022zbMath1287.68058MaRDI QIDQ2450928

Christopher Purcell, Vadim V. Lozin

Publication date: 26 May 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.01.022

zbMATH Keywords

NP-completeness; satisfiability; theory of computation; boundary properties of graphs

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, Critical hereditary graph classes: a survey, Upper domination: towards a dichotomy through boundary properties, Role colouring graphs in hereditary classes, Between clique-width and linear clique-width of bipartite graphs, A Boundary Property for Upper Domination

Cites Work

• Unnamed Item
• Boundary properties of graphs for algorithmic graph problems
• A simplified NP-complete satisfiability problem
• The Euclidean traveling salesman problem is NP-complete
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A special planar satisfiability problem and a consequence of its NP- completeness
• NP-hard graph problems and boundary classes of graphs
• Satisfiability of Acyclic and almost Acyclic CNF Formulas (II)
• Planar Formulae and Their Uses
• Determining the thickness of graphs is NP-hard
• On the Complexity of Timetable and Multicommodity Flow Problems
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A Computing Procedure for Quantification Theory
• The complexity of theorem-proving procedures