Edge-disjoint packings of graphs

DOI10.1016/0166-218X(92)00153-DzbMath0793.68114MaRDI QIDQ1326750

S. Louis Hakimi, Shigeru Masuyama, Derek Gordon Corneil

Publication date: 8 June 1994

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

zbMATH Keywords

NP-completeedge-disjoint packings of graphs

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 (5)

Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial ⋮ Edge-packing planar graphs by cyclic graphs ⋮ On the complexity of some edge-partition problems for graphs ⋮ Polynomial cases of graph decomposition: A complete solution of Holyer's problem ⋮ On some multigraph decomposition problems and their computational complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the decomposition of graphs into isomorphic matchings
• Chain packing in graphs
• The complexity of generalized clique packing
• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• NP-completeness of graph decomposition problems
• On the Complexity of General Graph Factor Problems
• The NP-Completeness of Some Edge-Partition Problems
• Paths, Trees, and Flowers

This page was built for publication: Edge-disjoint packings of graphs