Improved Algorithms for the 2-Vertex Disjoint Paths Problem

DOI10.1007/978-3-540-95891-8_49zbMath1206.68243OpenAlexW1549956213MaRDI QIDQ3599102

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 theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Linear time algorithms for two disjoint paths problems on directed acyclic graphs ⋮ The disjoint paths problem in quadratic time

Cites Work

• Unnamed Item
• A simple solution to the two paths problem in planar graphs
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Graph minors. XIII: The disjoint paths problem
• Solving the 2-disjoint paths problem in nearly linear time
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Finding k Disjoint Paths in a Directed Planar Graph
• Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH

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