Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
From MaRDI portal
Publication:2563924
DOI10.1016/0166-218X(95)00111-4zbMath0865.68089MaRDI QIDQ2563924
Publication date: 6 January 1997
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the planar integer two-flow problem
- Disjoint paths in graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A fast algorithm for maximum integral two-commodity flow in planar graphs
- Flow in planar graphs with vertex capacities
- Integer plane multiflows with a mixed number of demands
- Graph minors. XIII: The disjoint paths problem
- On the complexity of the disjoint paths problem
- Selecting and sequencing tests in adaptive checkout processes
- Maximal Flow Through a Network
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- On Odd Cuts and Plane Multicommodity Flows
- A Polynomial Solution to the Undirected Two Paths Problem
- On the Complexity of Timetable and Multicommodity Flow Problems
- Matching, Euler tours and the Chinese postman
- Two commodity network flows and linear programming
- Multi-Commodity Network Flows
- Faster shortest-path algorithms for planar graphs