Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs

DOI10.1016/j.endm.2005.06.010zbMath1182.05069OpenAlexW2023160462MaRDI QIDQ3439308

Cédric Bentz

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2005.06.010

zbMATH Keywords

multicutsplanar graphsintegral multiflowsedge disjoint paths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (3)

Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ Disjoint paths in sparse graphs

Cites Work

• 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
• Paths, flows, and VLSI-layout. Proceedings of a meeting held from June 20 to July 1, 1988, at the University of Bonn, Germany
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Graph minors. XIII: The disjoint paths problem
• On the complexity of the disjoint paths problem
• Edge-disjoint paths in Planar graphs with constant congestion
• Approximate max-integral-flow/min-multicut theorems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

This page was built for publication: Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs