Pushing the frontier of minimality

DOI10.1016/J.TCS.2018.06.008MaRDI QIDQ1786605zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• On the minimal constraint satisfaction problem: complexity and generation
• On minimal constraint networks
• Characterising tractable constraints
• scientific article; zbMATH DE number 1008453
• scientific article; zbMATH DE number 1234562

Cites work

• Consistency restoration and explanations in dynamic CSPs---Application to configuration
• Every planar map is four colorable. II: Reducibility
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Handbook of constraint programming.
• Networks of constraints: Fundamental properties and applications to picture processing
• On minimal constraint networks
• On the minimal constraint satisfaction problem: complexity and generation
• The complexity of satisfiability problems

Cited in

(5)

• Minimalism and paradoxes
• Extremal CSPs
• Super-reparametrizations of weighted CSPs: properties and optimization perspective
• On minimal constraint networks
• On the minimal constraint satisfaction problem: complexity and generation

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

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