Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
From MaRDI portal
Publication:1354723
DOI10.1006/jctb.1996.1735zbMath0868.05041OpenAlexW2058339086MaRDI QIDQ1354723
Publication date: 3 June 1997
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1996.1735
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (7)
Edge decompositions and rooted packings of graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ On Rooted Packings, Decompositions, and Factors of Graphs ⋮ Multigraph decomposition into stars and into multistars ⋮ Polynomial cases of graph decomposition: A complete solution of Holyer's problem ⋮ Edge decompositions into two kinds of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- On the Complexity of General Graph Factor Problems
- 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: Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
