Browsing Combinatorics and Optimization by Author "Berger, Eli"
Now showing items 1-1 of 1
-
Finding an induced path that is not a shortest path
Berger, Eli; Seymour, Paul; Spirkl, Sophie (Elsevier, 2021-07)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.