Compaction, Retraction, and Constraint Satisfaction
From MaRDI portal
Publication:4651492
DOI10.1137/S0097539701397801zbMath1101.68612MaRDI QIDQ4651492
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (13)
Coloring problems on bipartite graphs of small diameter ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ 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 ⋮ A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
This page was built for publication: Compaction, Retraction, and Constraint Satisfaction
