Multicommodity flows in planar graphs
From MaRDI portal
Publication:1154916
DOI10.1016/S0095-8956(81)80012-3zbMath0465.90029MaRDI QIDQ1154916
Publication date: 1981
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10)
Related Items
A Mixed Integer Model for the Sparsest Cut problem ⋮ Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ Euclidean maximum matchings in the plane -- local to global ⋮ A note on multiflows and treewidth ⋮ Eulerian disjoint paths problem in grid graphs is NP-complete ⋮ Channel routing in knock-knee mode: Simplified algorithms and proofs ⋮ The weighted link ring loading problem ⋮ Edge-disjoint homotopic paths in a planar graph with one hole ⋮ Linkage on the infinite grid ⋮ Coarse differentiation and multi-flows in planar graphs ⋮ NP-completeness of some edge-disjoint paths problems ⋮ On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary ⋮ Improved bounds on the max-flow min-cut ratio for multicommodity flows ⋮ Metric Embedding via Shortest Path Decompositions ⋮ A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Three commodity flows in graphs ⋮ Algorithms for multicommodity flows in planar graphs ⋮ On fractional multicommodity flows and distance functions ⋮ Distances and cuts in planar graphs ⋮ Optimum path packing on wheels: The consecutive case ⋮ When Do Gomory--Hu Subtrees Exist? ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Cut-sufficient directed 2-commodity multiflow topologies ⋮ On Canonical Concurrent Flows, Crossing Number and Graph Expansion ⋮ An improved algorithm for finding maximum outerplanar subgraphs ⋮ Improved approximations for the minimum-cut ratio and the flux ⋮ Multiflow Feasibility: An Annotated Tableau ⋮ Edge-disjoint paths in a grid bounded by two nested rectangles ⋮ Pathwidth, trees, and random embeddings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Klein bottle and multicommodity flows ⋮ On complexity, representation and approximation of integral multicommodity flows ⋮ The ellipsoid method and its consequences in combinatorial optimization ⋮ Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ Network design with a discrete set of traffic matrices ⋮ Criticality for multicommodity flows ⋮ The hardness of routing two pairs on one face ⋮ An algorithm for node-capacitated ring routing ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ On obstructions to small face covers in planar graphs ⋮ Parity conditions in homotopic knock-knee routing ⋮ Isometric embedding of Busemann surfaces into \(L_1\) ⋮ Algorithms for routing around a rectangle ⋮ Disjoint paths in sparse graphs ⋮ Ideal clutters ⋮ On local routing of two-terminal nets ⋮ A cycle augmentation algorithm for minimum cost multicommodity flows on a ring ⋮ An efficient algorithm for packing cuts and \((2,3)\)-metrics in a planar graph with three holes ⋮ A polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting ⋮ Multicommodity flows in cycle graphs ⋮ A Note on the Ring Loading Problem ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ 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 ⋮ A minimax theorem on circuits in projective graphs ⋮ Unnamed Item ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ On max-flow min-cut and integral flow properties for multicommodity flows in directed networks ⋮ A node-capacitated Okamura-Seymour theorem ⋮ Multicommodity flows in certain planar directed networks ⋮ Decomposition of graphs on surfaces and a homotopic circulation theorem ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Approximations for the disjoint paths problem in high-diameter planar networks ⋮ Switchbox routing in VLSI design: Closing the complexity gap ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ Projections of the capacitated network loading problem ⋮ Multicommodity flows in graphs ⋮ A linear-time algorithm for edge-disjoint paths in planar graphs ⋮ Half-integral flows in a planar graph with four holes ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ Disjoint paths in a rectilinear grid ⋮ A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works ⋮ A generalization of outerplanar graphs ⋮ Routings for involutions of a hypercube ⋮ Edge-disjoint paths in planar graphs ⋮ Algorithms for routing in planar graphs
Cites Work
