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

coloringcompactioncomputational complexitygraph algorithmsgraph partitionhomomorphism

Mathematics Subject Classification ID

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

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

(16)

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

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)