Packing directed cycles efficiently

DOI10.1016/j.dam.2006.04.033zbMath1129.05035OpenAlexW2005943912MaRDI QIDQ867851

Zeev Nutov, Raphael Yuster

Publication date: 19 February 2007

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

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.033

zbMATH Keywords

polynomial algorithmlinear programsimple digraphdicycle packing numberdirected regularity lemmafractional dicycle packing

Mathematics Subject Classification ID

Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

Packing and Covering a Given Directed Graph in a Directed Graph ⋮ Packing edge-disjoint triangles in regular and almost regular tournaments ⋮ Packing and covering directed triangles asymptotically ⋮ Packing Triangles in Regular Tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly-perfect hypergraph packing is in NC
• Integer and fractional packings in dense graphs
• Near perfect coverings in graphs and hypergraphs
• Matchings and covers in hypergraphs
• On the integral dicycle packings and covers and the linear ordering polytope
• Packing directed circuits fractionally
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Constructive Quasi-Ramsey Numbers and Tournament Ranking
• The Algorithmic Aspects of the Regularity Lemma
• Integer and fractional packing of families of graphs
• Packing Digraphs with Directed Closed Trails
• Testing subgraphs in directed graphs

This page was built for publication: Packing directed cycles efficiently