Algorithms for partition of some class of graphs under compaction

DOI10.1007/978-3-642-22685-4_29MaRDI QIDQ3087960zbMATH OpenOpenAlexFDO

Authors 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

graph partitioncomputational complexitygraph algorithmshomomorphismcoloringcompaction

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• Computing and Combinatorics
• Computational complexity of compaction to irreflexive cycles
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Computational Complexity of Compaction to Reflexive Cycles

Cited in

(15)

• Disconnected cuts in claw-free graphs
• Graph partitions with prescribed patterns
• The complexity of surjective homomorphism problems-a survey
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• On the sum-max graph partitioning problem
• scientific article; zbMATH DE number 4094840 (Why is no real title available?)
• Finding vertex-surjective graph homomorphisms
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Comparison of algorithms in graph partitioning
• Computational complexity relationship between compaction, vertex-compaction, and retraction
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• Obstructions to partitions of chordal graphs

This page was built for publication: Algorithms for partition of some class of graphs under compaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3087960)