New algorithms for maximum disjoint paths based on tree-likeness

DOI10.1007/s10107-017-1199-3zbMath1401.68361arXiv1603.01740OpenAlexW2885925565WikidataQ59602738 ScholiaQ59602738MaRDI QIDQ1785205

Matthias Mnich, Krzysztof Fleszar, Joachim Spoerhase

Publication date: 28 September 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmfeedback vertex setdisjoint pathsfixed-parameter algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (4)

Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ On b-acyclic chromatic number of a graph ⋮ Walking through waypoints ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernel bounds for disjoint cycles and disjoint paths
• Primal-dual approximation algorithms for integral flow and multicut in trees
• A note on multiflows and treewidth
• On the parameterized complexity of multiple-interval graph problems
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Approximations for the disjoint paths problem in high-diameter planar networks
• Approximating disjoint-path problems using packing integer programs
• Graph minors. XIII: The disjoint paths problem
• The geometry of graphs and some of its algorithmic applications
• Flow-cut gaps for integer and fractional multiflows
• Edge-Disjoint Paths in Expander Graphs
• A shorter proof of the graph minor algorithm
• Tight Bounds for Linkages in Planar Graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
• Multicommodity demand flow in a tree and packing integer programs
• An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs
• The NP-Completeness of Edge-Coloring
• On the Computational Complexity of Combinatorial Problems
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• New hardness results for routing on disjoint paths
• Maximum Edge-Disjoint Paths in k-Sums of Graphs
• Improved approximation for node-disjoint paths in planar graphs
• On Routing Disjoint Paths in Bounded Treewidth Graphs
• Routing in undirected graphs with constant congestion
• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
• Edge Disjoint Paths in Moderately Connected Graphs
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

This page was built for publication: New algorithms for maximum disjoint paths based on tree-likeness