Criticality for multicommodity flows

DOI10.1016/J.JCTB.2014.08.001MaRDI QIDQ473104zbMATH OpenOpenAlexFDO

Authors Paul Seymour

Publication date 21 November 2014

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2014.08.001

zbMATH Keywords

multicommodity flowspolynomial-timetree-decomposition

Mathematics Subject Classification ID

Trees (05C05) Flows in graphs (05C21) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10)

Recommendations

• Half-integral five-terminus flows
• The maximum multiflow problems with bounded fractionality
• scientific article; zbMATH DE number 3947967
• Integer plane multiflows with a mixed number of demands
• On the 3-Commodity Flow Problem

Cites work

• A new polynomial-time algorithm for linear programming
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Combinatorial approaches to multiflow problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Disjoint paths in graphs
• Four-terminus flows
• Geometric algorithms and combinatorial optimization
• Graph minors. XIII: The disjoint paths problem
• Graph searching and a min-max theorem for tree-width
• Half-integral five-terminus flows
• Multi-Commodity Network Flows
• Multicommodity flows in planar graphs
• On Odd Cuts and Plane Multicommodity Flows
• On the complexity of the disjoint paths problem
• Quickly excluding a planar graph
• Rooted grid minors
• The directed subgraph homeomorphism problem
• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

Cited in

(9)

• Methods of the convex cone theory in the feasibility problem of multicommodity flow
• Multiple weak 2-linkage and its applications on integer flows of signed graphs
• scientific article; zbMATH DE number 3947966 (Why is no real title available?)
• scientific article; zbMATH DE number 1327275 (Why is no real title available?)
• Substitutes, complements, and ripples in multicommodity flows on suspension graphs
• On the 3-Commodity Flow Problem
• Multiflows in symmetric digraphs
• Immersion in four-edge-connected graphs
• The Klein bottle and multicommodity flows

This page was built for publication: Criticality for multicommodity flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q473104)