On planar valued CSPs

DOI10.1016/j.jcss.2017.03.005zbMath1370.68125arXiv1602.06323OpenAlexW2280355158MaRDI QIDQ2396724

Stanislav Živný, Peter Fulla

Publication date: 24 May 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.06323

zbMATH Keywords

planarityconstraint satisfactionvalued constraint satisfactionmultimorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tractability in constraint satisfaction problems: a survey
• Colouring, constraint satisfaction, and complexity
• The complexity of counting homomorphisms seen from the other side
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Constraints, consistency and closure
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The complexity of planar Boolean \#CSP with complex weights
• The complexity of soft constraint satisfaction
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Complexity of conservative constraint satisfaction problems
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• The Complexity of Finite-Valued CSPs
• Skew Bisubmodularity and Valued CSPs
• On Planar Boolean CSP
• A Galois Connection for Valued Constraint Languages of Infinite Size
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Sherali-Adams Relaxations for Valued CSPs
• Necessary Conditions for Tractability of Valued CSPs
• Effectiveness of Structural Restrictions for Hybrid CSPs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Minimum-weight triangulation is NP-hard
• Efficient Planarity Testing
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Even Delta-Matroids and the Complexity of Planar Boolean CSPs
• On Planar Valued CSPs
• The Complexity of Valued CSPs
• The Power of Linear Programming for General-Valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• Bounded Tree-Width and CSP-Related Problems
• The complexity of conservative valued CSPs
• An Algebraic Theory of Complexity for Discrete Optimization

This page was built for publication: On planar valued CSPs