Shortest paths between shortest paths

Marcin Kamiski; Paul Medvedev; Martin Milani

doi:10.1016/j.tcs.2011.05.021

Shortest paths between shortest paths

Marcin Kamiski, Paul Medvedev, Martin Milani

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

63 Scopus citations

Abstract

We study the following problem on reconfiguring shortest paths in graphs: Given two shortest st paths, what is the minimum number of steps required to transform one into the other, where each intermediate path must also be a shortest st path and must differ from the previous one by only one vertex. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length.

Original language	English (US)
Pages (from-to)	5205-5210
Number of pages	6
Journal	Theoretical Computer Science
Volume	412
Issue number	39
DOIs	https://doi.org/10.1016/j.tcs.2011.05.021
State	Published - Sep 9 2011

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2011.05.021

Cite this

@article{d1d1715c3e45424a90ab3e3a676cfeea,

title = "Shortest paths between shortest paths",

abstract = "We study the following problem on reconfiguring shortest paths in graphs: Given two shortest st paths, what is the minimum number of steps required to transform one into the other, where each intermediate path must also be a shortest st path and must differ from the previous one by only one vertex. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length.",

author = "Marcin Kamiski and Paul Medvedev and Martin Milani",

year = "2011",

month = sep,

day = "9",

doi = "10.1016/j.tcs.2011.05.021",

language = "English (US)",

volume = "412",

pages = "5205--5210",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "39",

}

TY - JOUR

T1 - Shortest paths between shortest paths

AU - Kamiski, Marcin

AU - Medvedev, Paul

AU - Milani, Martin

PY - 2011/9/9

Y1 - 2011/9/9

N2 - We study the following problem on reconfiguring shortest paths in graphs: Given two shortest st paths, what is the minimum number of steps required to transform one into the other, where each intermediate path must also be a shortest st path and must differ from the previous one by only one vertex. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length.

AB - We study the following problem on reconfiguring shortest paths in graphs: Given two shortest st paths, what is the minimum number of steps required to transform one into the other, where each intermediate path must also be a shortest st path and must differ from the previous one by only one vertex. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length.

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

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

U2 - 10.1016/j.tcs.2011.05.021

DO - 10.1016/j.tcs.2011.05.021

M3 - Article

AN - SCOPUS:80051672732

SN - 0304-3975

VL - 412

SP - 5205

EP - 5210

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 39

ER -

Shortest paths between shortest paths

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this