Finding an induced path that is not a shortest path

Eli Berger; Paul Seymour; Sophie Spirkl

doi:10.1016/j.disc.2021.112398

Finding an induced path that is not a shortest path

Eli Berger, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-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 language	American English
Article number	112398
Journal	Discrete Mathematics
Volume	344
Issue number	7
DOIs	https://doi.org/10.1016/j.disc.2021.112398
State	Published - Jul 2021

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Algorithm
Induced path
Shortest path

Access to Document

10.1016/j.disc.2021.112398

Cite this

@article{9e66e6d9448e4dc3b75000d215413d80,

title = "Finding an induced path that is not a shortest path",

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.",

keywords = "Algorithm, Induced path, Shortest path",

author = "Eli Berger and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = jul,

doi = "10.1016/j.disc.2021.112398",

language = "American English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "7",

}

TY - JOUR

T1 - Finding an induced path that is not a shortest path

AU - Berger, Eli

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2021/7

Y1 - 2021/7

N2 - 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.

AB - 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.

KW - Algorithm

KW - Induced path

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=85105342220&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105342220&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112398

DO - 10.1016/j.disc.2021.112398

M3 - Article

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 7

M1 - 112398

ER -

Finding an induced path that is not a shortest path

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this