A node-capacitated Okamura-Seymour theorem
From MaRDI portal
Publication:747769
DOI10.1007/s10107-014-0810-0zbMath1322.05068arXiv1209.2744OpenAlexW3121660951MaRDI QIDQ747769
Mohammad Moharrami, James R. Lee, Manor Mendel
Publication date: 19 October 2015
Published in: Mathematical Programming. Series A. Series B, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1209.2744
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21)
Related Items (3)
Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Multicommodity flows and cuts in polymatroidal networks
Cites Work
- Unnamed Item
- Unnamed Item
- Cuts, trees and \(\ell_1\)-embeddings of graphs
- The metrical interpretation of superreflexivity in Banach spaces
- Multicommodity flows in planar graphs
- Extending Lipschitz functions via random metric partitions
- The geometry of graphs and some of its algorithmic applications
- An algorithm for node-capacitated ring routing
- Measured descent: A new embedding method for finite metrics
- Multicommodity flows and cuts in polymatroidal networks
- Maximal Flow Through a Network
- Vertex cuts, random walks, and dimension reduction in series-parallel graphs
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Minimum cost flow with set-constraints
- Computing Maximal “Polymatroidal” Network Flows
- On the geometry of graphs with a forbidden minor
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- Excluded minors, network decomposition, and multicommodity flow
- Node-Capacitated Ring Routing
- Multi-Commodity Network Flows
- Vertex Sparsifiers: New Results from Old Techniques
- On dominated \(\ell_1\) metrics
This page was built for publication: A node-capacitated Okamura-Seymour theorem
