A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
From MaRDI portal
Publication:2575831
DOI10.1016/j.jcss.2004.07.003zbMath1101.68613OpenAlexW2051028069MaRDI QIDQ2575831
Publication date: 7 December 2005
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2004.07.003
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (15)
Unnamed Item ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Unnamed Item ⋮ The complexity of surjective homomorphism problems-a survey ⋮ On the sum-max graph partitioning problem ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Surjective \(H\)-colouring: new hardness results ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Finding vertex-surjective graph homomorphisms ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Retracting Graphs to Cycles ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computational complexity of compaction to irreflexive cycles
- Absolute reflexive retracts and absolute bipartite retracts
- A characterization of absolute retracts of n-chromatic graphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Colorings and interpretations: a connection between graphs and grammar forms
- Parallel concepts in graph theory
- Absolute retracts of bipartite graphs
- List homomorphisms and circular arc graphs
- Complexity of graph partition problems
- Absolute Retracts and Varieties of Reflexive Graphs
- Classification and detection of obstructions to planarity
- Fixed-edge theorem for graphs with loops
- A graph coloring algorithm for large scheduling problems
- An application of graph coloring to printed circuit testing
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- List Partitions
- Compaction, Retraction, and Constraint Satisfaction
- Computing and Combinatorics
- Computational Complexity of Compaction to Reflexive Cycles
- Monotone monadic SNP and constraint satisfaction
This page was built for publication: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results