An exact algorithm for the Boolean connectivity problem for \(k\)-CNF

DOI10.1016/j.tcs.2011.04.041zbMath1221.68104OpenAlexW2062843268MaRDI QIDQ638525

Masaki Yamamoto, Suguru Tamaki, Kazuhisa Makino

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)

Related Items

Shortest reconfiguration of sliding tokens on subclasses of interval graphs, Reconfiguration of maximum-weight \(b\)-matchings in a graph, Computational complexity of jumping block puzzles, Approximability of the subset sum reconfiguration problem, Linear-time algorithm for sliding tokens on trees, The complexity of dominating set reconfiguration, Reconfiguration of list \(L(2,1)\)-labelings in a graph, Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect, Computational complexity of jumping block puzzles, Shortest Reconfiguration of Sliding Tokens on a Caterpillar, Introduction to reconfiguration, On reconfigurability of target sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Boolean connectivity problem for Horn relations
• Solving satisfiability in less than \(2^ n\) steps
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• New upper bound for the \#3-SAT problem
• Dynamic Programming Treatment of the Travelling Salesman Problem
• The Travelling Salesman Problem in Bounded Degree Graphs
• An improved exponential-time algorithm for k -SAT
• Fourier meets M\"{o}bius: fast subset convolution
• Automata, Languages and Programming
• The Traveling-Salesman Problem and Minimum Spanning Trees
• STACS 2005
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies