Finding an induced path that is not a shortest path

2020/05/26 by Berger, Eli, Seymour, Paul, Spirkl, Sophie · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2005.12861

Abstract

We give a polynomial-time algorithm that, with input a graph G and two vertices u,v of G, decides whether there is an induced uv-path that is longer than the shortest uv-path.

Cited by

• A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs

Related

• Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)
• Long induced paths in a configuration model
• A Survey of Shortest-Path Algorithms
• Contracting to a Longest Path in H-Free Graphs
• Long Directed Detours: Reduction to 2-Disjoint Paths