Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
From MaRDI portal
Publication:924540
DOI10.1016/j.jda.2006.03.009zbMath1142.05324OpenAlexW2025762780MaRDI QIDQ924540
Marie-Christine Costa, Cédric Bentz, Frédéric Roupin
Publication date: 16 May 2008
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2006.03.009
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (3)
The shortest multipaths problem in a capacitated dense channel ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ Max-multiflow/min-multicut for G+H series-parallel
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Minimal multicut and maximal integer multiflow: a survey
- Disjoint paths in a rectilinear grid
- Edge-disjoint paths in planar graphs
- Multicommodity flows in planar graphs
- Eulerian disjoint paths problem in grid graphs is NP-complete
- Routing through a Dense Channel with Minimum Total Wire Length
- The Complexity of Multiterminal Cuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
This page was built for publication: Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs