An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

DOI10.1137/20M1319401zbMath1462.05112arXiv2001.01715OpenAlexW3154368416MaRDI QIDQ4986808

Claire Mathieu, Mathieu Mari, Chien-Chung Huang, 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 algorithmplanar graphsedge-disjoint paths

Mathematics Subject Classification ID

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

Related Items (2)

Approximating maximum integral multiflows on bounded genus graphs ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximate min-max relations for odd cycles in planar graphs
• Disjoint paths in sparse graphs
• On the integrality ratio for tree augmentation
• The directed subgraph homeomorphism problem
• The ellipsoid method and its consequences in combinatorial optimization
• Tight integral duality gap in the Chinese postman problem
• On two minimax theorems in graph
• Some simplified NP-complete graph problems
• The four-colour theorem
• Edge-disjoint odd cycles in planar graphs.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• Max-multiflow/min-multicut for G+H series-parallel
• On the complexity of the disjoint paths problem
• An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
• Multiflow Feasibility: An Annotated Tableau
• On Odd Cuts and Plane Multicommodity Flows
• On the Computational Complexity of Combinatorial Problems
• 2-Matchings and 2-covers of hypergraphs
• Potentials in Undirected Graphs and Planar Multiflows
• Matching, Euler tours and the Chinese postman
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• New hardness results for routing on disjoint paths
• Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation
• Almost polynomial hardness of node-disjoint paths in grids
• On Approximating Node-Disjoint Paths in Grids
• Improved approximation for node-disjoint paths in planar graphs
• Routing in undirected graphs with constant congestion
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

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