On some multigraph decomposition problems and their computational complexity

DOI10.1016/J.DISC.2003.07.005zbMath1076.68049OpenAlexW2168886174MaRDI QIDQ1827716

Michael Tarsi, Miri Priesler

Publication date: 6 August 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2003.07.005

zbMATH Keywords

NP-completenessDecompositionMultigraph

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ Multigraph decomposition into stars and into multistars

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the decomposition of graphs into isomorphic matchings
• NP-completeness of graph decomposition problems
• Edge-disjoint packings of graphs
• 3K2-decomposition of a graph
• The NP-Completeness of Some Edge-Partition Problems
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture

This page was built for publication: On some multigraph decomposition problems and their computational complexity