An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

DOI10.1137/20M1319401MaRDI QIDQ4986808zbMATH OpenOpenAlexFDO

Authors Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, Jens Vygen

Publication date 28 April 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.01715

zbMATH Keywords

approximation algorithmedge-disjoint pathsplanar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Abstract: We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges form a planar graph. By planar duality this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

Recommendations

• A linear-time algorithm for edge-disjoint paths in planar graphs
• An O( n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
• scientific article; zbMATH DE number 780786
• Exact algorithms for finding partial edge-disjoint paths
• On the complexity of the planar directed edge-disjoint paths problem
• Improved approximation for node-disjoint paths in planar graphs
• A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
• A tight lower bound for edge-disjoint paths on planar DAGs
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• An exponential time parameterized algorithm for planar disjoint paths

Cites work

• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 878892 (Why is no real title available?)
• scientific article; zbMATH DE number 910915 (Why is no real title available?)
• 2-Matchings and 2-covers of hypergraphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Almost polynomial hardness of node-disjoint paths in grids
• An O( n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximate min-max relations for odd cycles in planar graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Disjoint paths in sparse graphs
• Edge-disjoint odd cycles in planar graphs.
• Graph minors. XIII: The disjoint paths problem
• Graphs on surfaces
• Improved approximation for node-disjoint paths in planar graphs
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Matching, Euler tours and the Chinese postman
• Max-multiflow/min-multicut for G+H series-parallel
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Multiflow Feasibility: An Annotated Tableau
• New hardness results for routing on disjoint paths
• On Odd Cuts and Plane Multicommodity Flows
• On approximating node-disjoint paths in grids
• On the Computational Complexity of Combinatorial Problems
• On the complexity of the disjoint paths problem
• On the integrality ratio for tree augmentation
• On two minimax theorems in graph
• Potentials in Undirected Graphs and Planar Multiflows
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Routing in undirected graphs with constant congestion
• Some simplified NP-complete graph problems
• The directed subgraph homeomorphism problem
• The ellipsoid method and its consequences in combinatorial optimization
• The four-colour theorem
• Tight integral duality gap in the Chinese postman problem

Cited in

(18)

• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• Maximum flows on disjoint paths
• Packing sets of paths, stars and triangles: tractability and approximability
• Approximating maximum integral multiflows on bounded genus graphs
• Approximating maximum integral multiflows on bounded genus graphs
• Improved approximation for node-disjoint paths in planar graphs
• scientific article; zbMATH DE number 2030041 (Why is no real title available?)
• Approximations for the disjoint paths problem in high-diameter planar networks
• A note on packing paths in planar graphs
• An O( n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• An improved integrality gap for disjoint cycles in planar graphs
• An O( n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs
• An exponential time parameterized algorithm for planar disjoint paths
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• Packing cycles in planar and bounded-genus graphs

This page was built for publication: An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4986808)