Towards a solution of the Holyer's problem

DOI10.1007/3-540-57899-4_48MaRDI QIDQ6143972zbMATH OpenOpenAlexFDO

Authors Zbigniew Lonc

Publication date 5 January 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57899-4_48

zbMATH Keywords

\(H\)-decomposition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Polynomial cases of graph decomposition: A complete solution of Holyer's problem
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• NP-completeness of graph decomposition problems
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• On some multigraph decomposition problems and their computational complexity

Cites work

• 3K2-decomposition of a graph
• A note on the decomposition of graphs into isomorphic matchings
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• scientific article; zbMATH DE number 3974987 (Why is no real title available?)
• scientific article; zbMATH DE number 3726401 (Why is no real title available?)
• scientific article; zbMATH DE number 47528 (Why is no real title available?)
• NP-completeness of graph decomposition problems
• On the Complexity of General Graph Factor Problems
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(4)

• Graph decomposition of slim graphs
• Supplement and improvement of Holly-Preismann scheme
• Edge decompositions and rooted packings of graphs
• Towards establishing the use of holons as an enquiry method

This page was built for publication: Towards a solution of the Holyer's problem

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