Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths

DOI10.1137/22m1527398zbMath1527.05048arXiv2007.12502OpenAlexW4385575359MaRDI QIDQ6171262

André Nichterlein, Matthias Bentert, Malte Renken, Philipp Zschoche

Publication date: 11 August 2023

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

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

zbMATH Keywords

geometrydynamic programminggraph algorithmsW[1-hardness]

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• The disjoint paths problem in quadratic time
• Strong computational lower bounds via parameterized complexity
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem
• Graph minors. XIII: The disjoint paths problem
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• Two disjoint shortest paths problem with non-negative edge length
• The undirected two disjoint shortest paths problem
• On the Computational Complexity of Combinatorial Problems
• Faster 2-Disjoint-Shortest-Paths Algorithm
• The Directed Disjoint Shortest Paths Problem
• Shortest Two Disjoint Paths in Polynomial Time
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths