A simple algorithm for multicuts in planar graphs with outer terminals
From MaRDI portal
Publication:1026166
DOI10.1016/j.dam.2008.11.010zbMath1197.05140MaRDI QIDQ1026166
Publication date: 24 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.11.010
05C10: Planar graphs; geometric and topological aspects of graph theory
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Edge-disjoint paths in planar graphs
- Graph minors. VI. Disjoint paths across a disc
- The planar multiterminal cut problem
- Multicommodity flows in planar graphs
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- Maximal Flow Through a Network
- Two-Connected Augmentation Problems in Planar Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- The Complexity of Multiterminal Cuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Multiway cuts in node weighted graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Combinatorial optimization. Theory and algorithms.