Generalisations of matrix partitions: complexity and obstructions
From MaRDI portal
Publication:6564025
DOI10.1016/j.tcs.2024.114652MaRDI QIDQ6564025
Mamadou Moustapha Kanté, Alexey Barsukov
Publication date: 28 June 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Colourings, homomorphisms, and partitions of transitive digraphs
- The complexity of surjective homomorphism problems-a survey
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- The complexity of locally injective homomorphisms
- Matrix partitions with finitely many obstructions
- Dualities in full homomorphisms
- On the complexity of H-coloring
- The number of submatrices of a given type in a Hadamard matrix and related results
- On the algebraic structure of combinatorial problems
- A closed set of normal orthogonal functions.
- Graph complexity
- On the density of trigraph homomorphisms
- On digraph coloring problems and treewidth duality
- On realizations of point determining graphs, and obstructions to full homomorphisms
- Graph partitions with prescribed patterns
- Matrix partitions of split graphs
- A finer reduction of constraint problems to digraphs
- Expander graphs and their applications
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- List Partitions
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- A Proof of the CSP Dichotomy Conjecture
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of conservative valued CSPs
- The complexity of satisfiability problems
- QCSP Monsters and the Demise of the Chen Conjecture
This page was built for publication: Generalisations of matrix partitions: complexity and obstructions
