The Time Complexity of Constraint Satisfaction

DOI10.1007/978-3-540-79723-4_18MaRDI QIDQ3503589zbMATH OpenOpenAlexFDO

Authors Patrick Traxler

Publication date 5 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79723-4_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Time complexity of constraint satisfaction via universal algebra
• Fine-grained time complexity of constraint satisfaction problems
• On the subexponential-time complexity of CSP
• An initial study of time complexity in infinite-domain constraint satisfaction
• Precise upper and lower bounds for the monotone constraint satisfaction problem

Cites work

• A condition for matchability in hypergraphs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• An LP-Designed Algorithm for Constraint Satisfaction
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Matching is as easy as matrix inversion
• NP is as easy as detecting unique solutions
• On the complexity of k-SAT
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Which problems have strongly exponential complexity?
• Worst-case time bounds for coloring and satisfiability problems

Cited in

(24)

• Channel assignment via fast zeta transform
• General lower bounds and improved algorithms for infinite-domain CSPs
• Assigning channels via the meet-in-the-middle approach
• Precise upper and lower bounds for the monotone constraint satisfaction problem
• New Plain-Exponential Time Classes for Graph Homomorphism
• The parity of set systems under random restrictions with applications to exponential time problems
• Lower bounds for the graph homomorphism problem
• scientific article; zbMATH DE number 1222101 (Why is no real title available?)
• scientific article; zbMATH DE number 1555929 (Why is no real title available?)
• Why are CSPs based on partition schemes computationally hard?
• A separator theorem for hypergraphs and a CSP-SAT algorithm
• Refining complexity analyses in planning by exploiting the exponential time hypothesis
• Fine-grained time complexity of constraint satisfaction problems
• Testing the Complexity of a Valued CSP Language
• Time complexity of constraint satisfaction via universal algebra
• An initial study of time complexity in infinite-domain constraint satisfaction
• On the subexponential-time complexity of CSP
• Derandomizing isolation in space-bounded settings
• On super strong ETH
• New plain-exponential time classes for graph homomorphism
• Computation of Hadwiger number and related contraction problems: tight lower bounds
• Counting homomorphisms in plain exponential time
• Faster algorithm for unique (k,2)-CSP
• Algorithms and complexity of difference logic

This page was built for publication: The Time Complexity of Constraint Satisfaction

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