Computational Complexity of Compaction to Reflexive Cycles

DOI10.1137/S0097539701383522zbMath1029.68085MaRDI QIDQ4706192

Narayan Vikas

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational complexity; graph; retraction; homomorphism; coloring; compaction

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Covering Graphs with Few Complete Bipartite Subgraphs, Algorithms for partition of some class of graphs under compaction and vertex-compaction, Obstructions to partitions of chordal graphs, The complexity of surjective homomorphism problems-a survey, Colouring, constraint satisfaction, and complexity, Computational complexity of compaction to irreflexive cycles, Parameterizing cut sets in a graph by the number of their components, Computing vertex-surjective homomorphisms to partially reflexive trees, Finding vertex-surjective graph homomorphisms, Covering graphs with few complete bipartite subgraphs, Surjective \(H\)-colouring: new hardness results, The computational complexity of disconnected cut and \(2 K_2\)-partition, On disconnected cuts and separators, On the sum-max graph partitioning problem, Graph partitions with prescribed patterns, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees