An exact algorithm for the Boolean connectivity problem for k-CNF

DOI10.1016/J.TCS.2011.04.041MaRDI QIDQ638525zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Publication date 12 September 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.04.041

zbMATH Keywords

Boolean connectivityCNF satisfiabilityexponential-time algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On k-positive satisfiability problem
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

Cites work

• A probabilistic algorithm for k-SAT based on limited local search and restart
• An improved exponential-time algorithm for k -SAT
• Automata, Languages and Programming
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Fourier meets M\"{o}bius: fast subset convolution
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 2119676 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT
• New upper bound for the \#3-SAT problem
• On the Boolean connectivity problem for Horn relations
• Solving satisfiability in less than \(2^ n\) steps
• STACS 2005
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The Travelling Salesman Problem in Bounded Degree Graphs

Cited in

(17)

• On reconfigurability of target sets
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Introduction to reconfiguration
• Reconfiguration of maximum-weight b-matchings in a graph
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Computational complexity of jumping block puzzles
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• A computational trichotomy for connectivity of Boolean satisfiability
• On the Boolean Connectivity Problem for Horn Relations
• Approximability of the subset sum reconfiguration problem
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Linear-time algorithm for sliding tokens on trees
• The complexity of dominating set reconfiguration
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Computational complexity of jumping block puzzles
• Some results on vertex separator reconfiguration
• Exact algorithms and hardness result for the Boolean connectivity problem of k-Horn formulas

This page was built for publication: An exact algorithm for the Boolean connectivity problem for \(k\)-CNF

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