Matroids and multicommodity flows

DOI10.1016/S0195-6698(81)80033-9zbMath0479.05023OpenAlexW1985284097MaRDI QIDQ1161527

Publication date: 1981

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0195-6698(81)80033-9

zbMATH Keywords

max-flow min-cut theorem excluded minor regular matroid multiple commodity flow

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

On the cycle polytope of a binary matroid, A generalized cut-condition for multiflows in matroids, Idealness of k-wise Intersecting Families, On the complexity of the disjoint paths problem, Decomposition and optimization over cycles in binary matroids, A survey on flows in graphs and matroids, Applications of cut polyhedra. II, Compositions for matroids with the Fulkerson property, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Antisymmetric flows in matroids, Colouring series-parallel graphs, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, Total dual dyadicness and dyadic generating sets, Hilbert bases of cuts, Polyhedra of regular p-nary group problems, Compressed polytopes and statistical disclosure limitation, Generalized cut and metric polytopes of graphs and simplicial complexes, A connection between positive semidefinite and Euclidean distance matrix completion problems, When Do Gomory--Hu Subtrees Exist?, One-third-integrality in the max-cut problem, On combinatorial properties of binary spaces, Trader multiflow and box-TDI systems in series-parallel graphs, Odd Solutions to Systems of Inequalities Coming From Regular Chain Groups, Cut-sufficient directed 2-commodity multiflow topologies, Decomposition of regular matroids, On Hilbert bases of cuts, Detecting minors in matroids through triangles, Dual row modules and polyhedra of blocking group problems, Templates for Binary Matroids, The Excluded Minors for Isometric Realizability in the Plane, Spanning cycles in regular matroids without small cocircuits, Unnamed Item, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, A polyhedral approach to an integer multicommodity flow problem, Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors, Cuboids, a class of clutters, The hypermetric cone and polytope on eight vertices and some generalizations, Pfaffian graphs, \(T\)-joins and crossing numbers, On ideal clutters, metrics and multiflows, Tight integral duality gap in the Chinese postman problem, Compositions in the bipartite subgraph polytope, Lattice flows in networks, On cuts and matchings in planar graphs, Ideal clutters, Perfect, ideal and balanced matrices, Multiperiod network design with incremental routing, Graphs with the Circuit Cover Property, Max-multiflow/min-multicut for G+H series-parallel, Minimum cycle coverings and integer flows, Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, Nowhere zero 4‐flow in regular matroids, Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators, Enumeration of the facets of cut polytopes over some highly symmetric graphs, Paintshop, odd cycles and necklace splitting, On the cut polytope, Master polytopes for cycles of binary matroids, Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions, Projections of the capacitated network loading problem, A characterization of weakly bipartite graphs, Idealness of \(k\)-wise intersecting families

Cites Work