Min-max Relations for Directed Graphs

DOI10.1016/S0304-0208(08)72456-3zbMath0497.05029MaRDI QIDQ3960724

Alexander Schrijver

Publication date: 1982

Published in: North-Holland Mathematics Studies (Search for Journal in Brave)

zbMATH Keywords

Menger's theoremstrong cutEdmonds' branching theorempairwise disjoint strong connectors

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

Efficient many-to-Many point matching in one dimension, Disjoint dijoins for classes of dicuts in finite and infinite digraphs, Stronger bounds and faster algorithms for packing in generalized kernel systems, Directed cut transversal packing for source-sink connected graphs, A Las Vegas RNC algorithm for maximum matching, Partitioning series-parallel multigraphs into \(v^*\)-excluding edge covers, Shortest bibranchings and valuated matroid intersection, On Packing Dijoins in Digraphs and Weighted Digraphs, The b‐bibranching problem: TDI system, packing, and discrete convexity, Vertex-disjoint paths and edge-disjoint branchings in directed graphs, An efficient scaling algorithm for the minimum weight bibranching problem, Equitable partitions into matchings and coverings in mixed graphs, Proving total dual integrality with cross-free families—A general framework, Relationship of two formulations for shortest bibranchings, Packing in generalized kernel systems: a framework that generalizes packing of branchings, Complexity of packing common bases in matroids, An efficient algorithm for minimum-weight bibranching, On packing connectors, Packing and covering of crossing families of cuts, A family of perfect graphs associated with directed graphs