Packing directed cycles efficiently

DOI10.1016/J.DAM.2006.04.033MaRDI QIDQ867851zbMATH OpenOpenAlexFDO

Authors 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

dicycle packing numberdirected regularity lemmafractional dicycle packinglinear programpolynomial algorithmsimple digraph

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2004
• Packing directed cycles through a specified vertex set
• Packing cycles in graphs
• Packing cycles in undirected graphs
• On packing shortest cycles in graphs
• Packing directed circuits exactly
• Packing cycles in complete graphs
• Packing directed Hamilton cycles online
• Packing cycles through prescribed vertices
• Labeled packing of cycles and circuits

Cites work

• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Approximation algorithms for cycle packing problems
• Constructive Quasi-Ramsey Numbers and Tournament Ranking
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• Integer and fractional packing of families of graphs
• Integer and fractional packings in dense graphs
• Matchings and covers in hypergraphs
• Near perfect coverings in graphs and hypergraphs
• Nearly-perfect hypergraph packing is in NC
• On the integral dicycle packings and covers and the linear ordering polytope
• Packing Digraphs with Directed Closed Trails
• Packing directed circuits fractionally
• Testing subgraphs in directed graphs
• The Algorithmic Aspects of the Regularity Lemma
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(14)

• Directed cut transversal packing for source-sink connected graphs
• On integrality, stability and composition of dicycle packings and covers
• Packing directed circuits fractionally
• Packing and covering directed triangles asymptotically
• Packing cycles through prescribed vertices
• Packing triangles in regular tournaments
• How to Pack Directed Acyclic Graphs into Small Blocks
• scientific article; zbMATH DE number 3926962 (Why is no real title available?)
• Packing cycles exactly in polynomial time
• Packing edge-disjoint triangles in regular and almost regular tournaments
• Packing directed circuits through prescribed vertices bounded fractionally
• Mathematical Foundations of Computer Science 2004
• Packing and Covering a Given Directed Graph in a Directed Graph
• Packing directed circuits exactly

This page was built for publication: Packing directed cycles efficiently

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