Multicommodity flows in planar graphs
From MaRDI portal
Publication:1154916
Cites work
Cited in
(93)- A simple algorithm for multicuts in planar graphs with outer terminals
- Disjoint paths in a rectilinear grid
- Edge-disjoint paths in planar graphs
- Algorithms for routing in planar graphs
- Channel routing in knock-knee mode: Simplified algorithms and proofs
- Edge-disjoint homotopic paths in a planar graph with one hole
- Algorithms for multicommodity flows in planar graphs
- On fractional multicommodity flows and distance functions
- Distances and cuts in planar graphs
- The ellipsoid method and its consequences in combinatorial optimization
- On obstructions to small face covers in planar graphs
- Parity conditions in homotopic knock-knee routing
- Algorithms for routing around a rectangle
- On local routing of two-terminal nets
- A minimax theorem on circuits in projective graphs
- On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
- Approximations for the disjoint paths problem in high-diameter planar networks
- Switchbox routing in VLSI design: Closing the complexity gap
- A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works
- Routings for involutions of a hypercube
- Projections of the capacitated network loading problem
- Linkage on the infinite grid
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut 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
- Eulerian disjoint paths problem in grid graphs is NP-complete
- NP-completeness of some edge-disjoint paths problems
- Improved bounds on the max-flow min-cut ratio for multicommodity flows
- Optimum path packing on wheels: The consecutive case
- On complexity, representation and approximation of integral multicommodity flows
- An efficient algorithm for packing cuts and (2,3)-metrics in a planar graph with three holes
- Maximum edge-disjoint paths in planar graphs with congestion 2
- Integer plane multiflow maximisation: one-quarter-approximation and gaps
- On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary
- A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
- Isometric embedding of Busemann surfaces into L₁
- Pathwidth, trees, and random embeddings
- Network design with a discrete set of traffic matrices
- An algorithm for node-capacitated ring routing
- Multicommodity flows in cycle graphs
- A note on the ring loading problem
- A mixed integer model for the sparsest cut problem
- Multiflow Feasibility: An Annotated Tableau
- A combinatorial algorithm for the planar multiflow problem with demands located on three holes
- On Canonical Concurrent Flows, Crossing Number and Graph Expansion
- All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
- Criticality for multicommodity flows
- Improved approximations for the minimum-cut ratio and the flux
- Multicommodity network flows: a survey. I: Applications and formulations
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Metric Embedding via Shortest Path Decompositions
- When do Gomory-Hu subtrees exist?
- Improved guarantees for vertex sparsification in planar graphs
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- 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
- Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
- A cycle augmentation algorithm for minimum cost multicommodity flows on a ring
- Three commodity flows in graphs
- Cut-sufficient directed 2-commodity multiflow topologies
- scientific article; zbMATH DE number 7765399 (Why is no real title available?)
- An improved algorithm for finding maximum outerplanar subgraphs
- Switchbox routing in VLSI design: closing the complexity gap (extended abstract)
- A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
- The hardness of routing two pairs on one face
- Euclidean maximum matchings in the plane -- local to global
- Integer and unsplittable multiflows in series-parallel digraphs
- Unsplittable multicommodity flows in outerplanar graphs
- An approximate generalization of the Okamura-Seymour theorem
- Optimal padded decomposition for bounded treewidth graphs
- Rerouting planar curves and disjoint paths
- A mathematical programming approach for recognizing binet matrices
- O(1) Steiner point removal in series-parallel graphs
- Small additive error for unsplittable multicommodity flow in outerplanar graphs
- Ideal clutters
- Cut-sufficient directed 2-commodity multiflow topologies
- A face cover perspective to _1 embeddings of planar graphs
- On sparse covers of minor free graphs, low dimensional metric embeddings, and other applications
- Multicommodity flows in certain planar directed networks
- Decomposition of graphs on surfaces and a homotopic circulation theorem
- A generalization of outerplanar graphs
- Euclidean maximum matchings in the plane -- local to global
- A note on multiflows and treewidth
- The weighted link ring loading problem
- Coarse differentiation and multi-flows in planar graphs
- Edge-disjoint paths in a grid bounded by two nested rectangles
- The Klein bottle and multicommodity flows
- 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
- Disjoint paths in sparse graphs
- A polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting
This page was built for publication: Multicommodity flows in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1154916)
