Publication:867851

DOI10.1016/J.DAM.2006.04.033zbMATH Open1129.05035OpenAlexW2005943912MaRDI QIDQ867851FDOQ867851

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) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) 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)

Cites Work

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

Cited In (8)

• Packing triangles in regular tournaments
• Packing and Covering a Given Directed Graph in a Directed Graph
• Packing edge-disjoint triangles in regular and almost regular tournaments
• Directed cut transversal packing for source-sink connected graphs
• How to Pack Directed Acyclic Graphs into Small Blocks
• Packing and covering directed triangles asymptotically
• Packing cycles through prescribed vertices
• Packing directed circuits exactly

Recommendations

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

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)