Boundary properties of the satisfiability problems
From MaRDI portal
Publication:2450928
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
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