Directed cut transversal packing for source-sink connected graphs
From MaRDI portal
A proof is given for the side coboundaries of a graph concerning the conjecture that in every directed graph, a maximum packing of directed cut transversals is equal in cardinality to a minimum directed cut. It first reduces the problem to a packing theorem for bi-transversals, and then constructs a packing of bi-transversals of the required size, one edge at a time, by maintaining a Hall-like feasibility condition as each edge is added.
Recommendations
- Packing cuts in undirected graphs
- Packing cycles and cuts in undirected graphs
- Packing multiway cuts in capacitated graphs
- Packing disjoint cycles over vertex cuts
- A branch-price-and-cut algorithm for packing cuts in undirected graphs
- Packing directed cycles efficiently
- Packing directed cycles efficiently
- Directed Steiner tree packing and directed tree connectivity
- Packing directed cycles through a specified vertex set
Cites work
- A Minimax Theorem for Directed Graphs
- scientific article; zbMATH DE number 3752872 (Why is no real title available?)
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- scientific article; zbMATH DE number 3304771 (Why is no real title available?)
- Min-max Relations for Directed Graphs
- On two minimax theorems in graph
- The matroids with the max-flow min-cut property
Cited in
(12)- Complexity of packing common bases in matroids
- Packing in generalized kernel systems: a framework that generalizes packing of branchings
- Note on a min-max conjecture of Woodall
- Stronger bounds and faster algorithms for packing in generalized kernel systems
- Intersection properties of maximal directed cuts in digraphs
- Disjoint dijoins for classes of dicuts in finite and infinite digraphs
- On Packing Dijoins in Digraphs and Weighted Digraphs
- A min-max relation on dicuts and dijoins in weighted chordal digraphs
- Towards a dual version of Woodall's conjecture for partial 3-trees
- Packing and covering of crossing families of cuts
- A family of perfect graphs associated with directed graphs
- Partitioning series-parallel multigraphs into v^*-excluding edge covers
This page was built for publication: Directed cut transversal packing for source-sink connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101126)