Oriented star packings

DOI10.1016/J.JCTB.2007.09.004MaRDI QIDQ2483479zbMATH OpenOpenAlexFDO

Authors Romeo Rizzi, Richard C. Brewster, Pavol Hell

Publication date 28 April 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2007.09.004

zbMATH Keywords

good characterizationmin-max theoremoriented starpacking problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Given a family \(S\) of oriented stars, an \(S\)-packing in a digraph \(D\) is a collection of vertex disjoint subgraphs of \(D\), each of which is isomorphic to a member of \(S\). The \(S\)-packing problem is to ascertain the maximum number of vertices of a host \(D\) that can be covered by an \(S\)-packing of \(D\). The paper shows a dichotomy for the decision version of the \(S\)-packing problem, giving an exact classification of which problems are polynomial time solvable and which are NP-complete. For the polynomial problem, it provides Hall type min-max theorems, including versions for locally degree-constrained variants of the problems. It also shows that the \(S\)-packing problem is polynomial for some \(S\) and NP-complete otherwise.

Recommendations

• The superstar packing problem
• On star family packing of graphs
• Packing paths in digraphs
• scientific article; zbMATH DE number 568827
• On rooted packings, decompositions, and factors of graphs

Cites work

• A short proof of K�nig's matching theorem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Efficient subgraphs packing
• Graph packings
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• K�nig's edge coloring theorem without augmenting paths
• Matching theory
• On generalized matching problems
• On the complexity of digraph packings
• Packing paths in digraphs
• Packing subgraphs in a graph
• Packings by cliques and by finite families of graphs
• Packings by Complete Bipartite Graphs
• Paths, Trees, and Flowers

Cited in

(8)

• The superstar packing problem
• Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
• Equistarable bipartite graphs
• scientific article; zbMATH DE number 4180219 (Why is no real title available?)
• Packing paths in digraphs
• On star family packing of graphs
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Exact formulas for fixation probabilities on a complete oriented star

This page was built for publication: Oriented star packings

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