Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs

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

zbMATH Keywords

grid graphminimum multicutmaximum integer multiflow

Mathematics Subject Classification ID

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