Improved Algorithms for the 2-Vertex Disjoint Paths Problem

DOI10.1007/978-3-540-95891-8_49MaRDI QIDQ3599102zbMATH OpenOpenAlexFDO

Authors Torsten Tholey

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://nbn-resolving.org/urn:nbn:de:bvb:384-opus4-4837

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Improved algorithm for the half-disjoint paths problem
• An improved algorithm for the half-disjoint paths problem
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• Improved approximation algorithms for computing k disjoint paths subject to two constraints
• An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two
• STACS 2004
• Solving the 2-disjoint paths problem in nearly linear time
• Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph
• scientific article; zbMATH DE number 871922
• Improved algorithms for path partition and related problems

Cites work

• 2-linked graphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A Polynomial Solution to the Undirected Two Paths Problem
• A simple solution to the two paths problem in planar graphs
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• An improved algorithm for finding tree decompositions of small width
• Disjoint paths in graphs
• Finding k Disjoint Paths in a Directed Planar Graph
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3725714 (Why is no real title available?)
• Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout
• Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
• Solving the 2-disjoint paths problem in nearly linear time
• The directed subgraph homeomorphism problem

Cited in

(9)

• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph
• Computing vertex-disjoint paths in large graphs using MAOs
• Solving the 2-disjoint paths problem in nearly linear time
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• The disjoint paths problem in quadratic time
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two
• STACS 2004

This page was built for publication: Improved Algorithms for the 2-Vertex Disjoint Paths Problem

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