A new algorithm for optimal constraint satisfaction and its implications

DOI10.1007/978-3-540-27836-8_101MaRDI QIDQ5466451zbMATH OpenOpenAlexFDO

Authors Ryan Williams

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A new algorithm for optimal 2-constraint satisfaction and its implications
• An efficient algorithm for a class of constraint satisfaction problems
• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems
• A new approach to partial constraint satisfaction problems
• A new tractable class of constraint satisfaction problems
• On the efficient approximability of constraint satisfaction problems
• Principles and Practice of Constraint Programming – CP 2004
• Optimal satisfiability for propositional calculi and constraint satisfaction problems
• Constraint satisfaction problems: Algorithms and applications

Cited in

(28)

• Pathwidth of cubic graphs and exact algorithms
• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• An efficient algorithm for a class of constraint satisfaction problems
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• A CSP search algorithm with responsibility sets and kernels
• Open problems around exact algorithms
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Near-optimal algorithms for maximum constraint satisfaction problems
• scientific article; zbMATH DE number 6381632 (Why is no real title available?)
• Adaptive Constraint Satisfaction: The Quickest First Principle
• scientific article; zbMATH DE number 5575002 (Why is no real title available?)
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Towards hardness of approximation for polynomial time problems
• A new approach to partial constraint satisfaction problems
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Fast approximation of eccentricities and distances in hyperbolic graphs
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Fine-Grained Complexity of Regular Path Queries
• An exact algorithm for the Boolean connectivity problem for k-CNF
• Hardness of approximate diameter: now for undirected graphs
• Fine-grained complexity of regular path queries
• An asymptotically fast polynomial space algorithm for Hamiltonicity detection in sparse directed graphs
• Exponential-time approximation (schemes) for vertex-ordering problems
• Optimal 2-constraint satisfaction via sum-product algorithms
• A faster polynomial-space algorithm for Max 2-CSP
• Solving connected dominating set faster than \(2^n\)

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: A new algorithm for optimal constraint satisfaction and its implications

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