Algorithms for Partition of Some Class of Graphs under Compaction

DOI10.1007/978-3-642-22685-4_29zbMath1353.05119MaRDI QIDQ3087960

Narayan Vikas

Publication date: 17 August 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22685-4_29

zbMATH Keywords

computational complexity; homomorphism; graph algorithms; coloring; graph partition; compaction

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon, Computational complexity relationship between compaction, vertex-compaction, and retraction, 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, Computing vertex-surjective homomorphisms to partially reflexive trees, Finding vertex-surjective graph homomorphisms, The computational complexity of disconnected cut and \(2 K_2\)-partition, On the sum-max graph partitioning problem, Graph partitions with prescribed patterns