Multigraph decomposition into stars and into multistars

DOI10.1016/J.DISC.2005.03.012MaRDI QIDQ2487986zbMATH OpenOpenAlexFDO

Authors Miri Priesler, Michael Tarsi

Publication date 17 August 2005

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessdecision problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Decompositions of complete multigraphs into stars of varying sizes
• Decomposition of the complete bipartite multigraph into cycles and stars
• scientific article; zbMATH DE number 2192170
• Decomposition of balanced complete bipartite multigraphs into multistars
• Edge decompositions into two kinds of graphs

Cites work

• scientific article; zbMATH DE number 47528 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• scientific article; zbMATH DE number 3517174 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A note on the decomposition of graphs into isomorphic matchings
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• NP-completeness of graph decomposition problems
• On some multigraph decomposition problems and their computational complexity
• Perfect path double covers of graphs
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(15)

• scientific article; zbMATH DE number 5237247 (Why is no real title available?)
• Decomposition of balanced complete bipartite multigraphs into multistars
• On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem
• Multigraph decomposition into multigraphs with two underlying edges
• Packing plane spanning graphs with short edges in complete geometric graphs
• The real truth about star designs
• Directed star decompositions of the complete directed graph
• Determination of the star valency of a graph
• Cyclic decompositions of \(\lambda K_n\) into LWO graphs
• Problems and invariants connected with bicliques and multicliques of graphs
• On cyclic near-Hamiltonian cycle system of the complete multigraph
• scientific article; zbMATH DE number 2192170 (Why is no real title available?)
• Decompositions of complete multigraphs into stars of varying sizes
• Colorful edge decomposition of graphs: some polynomial cases
• On decomposing regular graphs into isomorphic double-stars

This page was built for publication: Multigraph decomposition into stars and into multistars

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