Computational Complexity of Compaction to Reflexive Cycles
From MaRDI portal
Publication:4706192
DOI10.1137/S0097539701383522zbMath1029.68085MaRDI QIDQ4706192
Publication date: 19 June 2003
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 (23)
Unnamed Item ⋮ Computational complexity of compaction to irreflexive cycles ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Obstructions to partitions of chordal graphs ⋮ Disconnected cuts in claw-free graphs ⋮ Unnamed Item ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Colouring, constraint satisfaction, and complexity ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ On the sum-max graph partitioning problem ⋮ 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 ⋮ On disconnected cuts and separators ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Graph partitions with prescribed patterns ⋮ Covering Graphs with Few Complete Bipartite Subgraphs ⋮ Covering graphs with few complete bipartite subgraphs ⋮ 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: Computational Complexity of Compaction to Reflexive Cycles
