Pushing the frontier of minimality

DOI10.1016/j.tcs.2018.06.008zbMath1400.68088OpenAlexW2805411558WikidataQ129711130 ScholiaQ129711130MaRDI QIDQ1786605

Guillaume Escamocher, Barry O'Sullivan

Publication date: 24 September 2018

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

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

zbMATH Keywords

constraint satisfactionminimal CSPNP-hardness result

Mathematics Subject Classification ID

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

Related Items (1)

Super-reparametrizations of weighted CSPs: properties and optimization perspective

Cites Work

• Unnamed Item
• On minimal constraint networks
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Every planar map is four colorable. II: Reducibility
• Networks of constraints: Fundamental properties and applications to picture processing
• The complexity of satisfiability problems
• On the Minimal Constraint Satisfaction Problem: Complexity and Generation
• Consistency restoration and explanations in dynamic CSPs---Application to configuration

This page was built for publication: Pushing the frontier of minimality