Computational complexity classification of partition under compaction and retraction

DOI10.1007/978-3-540-27798-9_41MaRDI QIDQ4681200zbMATH OpenOpenAlexFDO

Authors Narayan Vikas

Publication date 15 June 2005

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

Full work available at URL https://doi.org/10.1007/b99243

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Computational complexity relationship between compaction, vertex-compaction, and retraction
• Computational complexity relationship between compaction, vertex-compaction, and retraction
• Compaction, Retraction, and Constraint Satisfaction
• Algorithms for partition of some class of graphs under compaction and vertex-compaction

Cited in

(10)

• On the sum-max graph partitioning problem
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Algorithms for partition of some class of graphs under compaction
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Compaction to Reflexive Cycles
• Algebra and the complexity of digraph CSPs: a survey
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Computational complexity relationship between compaction, vertex-compaction, and retraction
• Computational complexity relationship between compaction, vertex-compaction, and retraction

This page was built for publication: Computational complexity classification of partition under compaction and retraction

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