Quantified Constraint Satisfaction Problem on Semicomplete Digraphs
From MaRDI portal
Publication:5278200
DOI10.1145/3007899zbMath1367.68115OpenAlexW2605983742MaRDI QIDQ5278200
Barnaby Martin, Petar Marković, Petar Đapić
Publication date: 13 July 2017
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/20046/1/20046.pdf
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maltsev digraphs have a majority polymorphism
- The complexity of constraint satisfaction games and QCSP
- Relatively quantified constraint satisfaction
- On the complexity of H-coloring
- Closed systems of functions and predicates
- Meditations on Quantified Constraint Satisfaction
- On Maltsev Digraphs
- Retractions to Pseudoforests
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Complexity of Colouring by Semicomplete Digraphs
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
- Duality and Polynomial Testing of Tree Homomorphisms
- QCSP on Partially Reflexive Cycles – The Wavy Line of Tractability
- Classifying the Complexity of Constraints Using Finite Algebras
- Quantified Equality Constraints
- The complexity of satisfiability problems
- Logical Approaches to Computational Barriers
This page was built for publication: Quantified Constraint Satisfaction Problem on Semicomplete Digraphs
