Finding an induced path that is not a shortest path

Eli Berger, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number112398
JournalDiscrete Mathematics
Volume344
Issue number7
DOIs
StatePublished - Jul 2021

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Algorithm
  • Induced path
  • Shortest path

Fingerprint

Dive into the research topics of 'Finding an induced path that is not a shortest path'. Together they form a unique fingerprint.

Cite this