On Odd Cuts and Plane Multicommodity Flows
From MaRDI portal
Publication:3893626
DOI10.1112/plms/s3-42.1.178zbMath0447.90026OpenAlexW2028436310MaRDI QIDQ3893626
Publication date: 1981
Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/plms/s3-42.1.178
Related Items
A note on the half-integral multiflow-problem restricted to minor-closed classes of graphs, Families of cuts with the MFMC-property, Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation, Conservative weightings and ear-decompositions of graphs, On the complexity of the disjoint paths problem, On Dyadic Fractional Packings of $T$-Joins, A quick proof of Seymour's theorem on t-joins, A survey on flows in graphs and matroids, How to tidy up a symmetric set-system by use of uncrossing operations, On the integral 4-packing of \(T\)-cuts, Undirected distances and the postman-structure of graphs, The Schrijver system of odd join polyhedra, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, Three commodity flows in graphs, On fractional multicommodity flows and distance functions, Distances and cuts in planar graphs, Approximate min-max relations for odd cycles in planar graphs, Minimum weight \((T,d)\)-joins and multi-joins, The disjoint shortest paths problem, A characterization of Seymour graphs, A characterization of minimal non-Seymour graphs, Approximating maximum integral multiflows on bounded genus graphs, Packing odd circuits in Eulerian graphs, Disjoint paths in graphs, Improved approximations for the minimum-cut ratio and the flux, Multicommodity flows in planar graphs, Multiflow Feasibility: An Annotated Tableau, Matroids and multicommodity flows, Unnamed Item, On a min--max theorem on bipartite graphs, Edge-disjoint odd cycles in planar graphs., Tree metrics and edge-disjoint \(S\)-paths, Criticality for multicommodity flows, Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems, An Excluded Minor Characterization of Seymour Graphs, A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs, Tight integral duality gap in the Chinese postman problem, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, On cuts and matchings in planar graphs, Finding thet-join structure of graphs, Ideal clutters, On shortest \(T\)-joins and packing \(T\)-cuts, Disjoint paths in graphs. (Reprint), On T-joins and odd factors, Packing and covering odd cycles in cubic plane graphs with small faces, Packing and covering odd cycles in cubic plane graphs with small faces, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs, On max-flow min-cut and integral flow properties for multicommodity flows in directed networks, On circuit decomposition of planar Eulerian graphs, On dual integrality in matching problems, Partitions into odd chains, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, Integer plane multiflow maximisation: one-quarter-approximation and gaps, Disjoint paths in a rectilinear grid, Vertex set partitions preserving conservativeness, A fast algorithm for maximum integral two-commodity flow in planar graphs, Packing paths in planar graphs, Edge-disjoint paths in planar graphs
