Algorithms for Partition of Some Class of Graphs under Compaction

DOI10.1007/978-3-642-22685-4_29zbMath1353.05119OpenAlexW171389261MaRDI 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 complexityhomomorphismgraph algorithmscoloringgraph partitioncompaction

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Obstructions to partitions of chordal graphs ⋮ Unnamed Item ⋮ The complexity of surjective homomorphism problems-a survey ⋮ On the sum-max graph partitioning problem ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Finding vertex-surjective graph homomorphisms ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Graph partitions with prescribed patterns ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon

This page was built for publication: Algorithms for Partition of Some Class of Graphs under Compaction