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

exponential-time algorithmsBoolean connectivityCNF satisfiability

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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
• STACS 2005
• Solving satisfiability in less than \(2^ n\) steps
• 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

(15)

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

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)