Multicommodity flows in graphs

DOI10.1016/0166-218X(83)90100-2MaRDI QIDQ1838904zbMATH OpenOpenAlexFDO

Authors Haruko Okamura

Publication date 1983

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(83)90100-2

zbMATH Keywords

planar graphmulticommodity flowsexistence of feasible flowsinteger-valued capacityinteger-valued demands

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Cites work

• Maximal Flow Through a Network
• Multi-Commodity Network Flows
• Multicommodity flows in planar graphs

Cited in

(15)

• Multicommodity network flows: a survey. I: Applications and formulations
• On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
• Three commodity flows in graphs
• The Klein bottle and multicommodity flows
• A combinatorial algorithm for the planar multiflow problem with demands located on three holes
• Half-integral flows in a planar graph with four holes
• Edge-disjoint homotopic paths in a planar graph with one hole
• Edge-disjoint paths in a grid bounded by two nested rectangles
• Algorithms for multicommodity flows in planar graphs
• An efficient algorithm for packing cuts and \((2,3)\)-metrics in a planar graph with three holes
• The hardness of routing two pairs on one face
• Packings of cuts realizing distances between certain vertices in a planar graph
• Distances and cuts in planar graphs
• On fractional multicommodity flows and distance functions
• Routing in grid graphs by cutting planes

This page was built for publication: Multicommodity flows in graphs

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