Shortest paths between shortest paths and independent sets

Marcin Kamiński; Paul Medvedev; Martin Milanič

doi:10.1007/978-3-642-19222-7_7

Shortest paths between shortest paths and independent sets

Marcin Kamiński, Paul Medvedev, Martin Milanič

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Scopus citations

Abstract

We study problems of reconfiguration of shortest paths in graphs. 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. Moreover, we also study reconfiguration of independent sets in three different models and analyze relationships between these models, observing that shortest path reconfiguration is a special case of independent set reconfiguration in perfect graphs, under any of the three models. Finally, we give polynomial results for restricted classes of graphs (even-hole-free and P₄-free graphs).

Original language	English (US)
Title of host publication	Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, Revised Selected Papers
Pages	56-67
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-19222-7_7
State	Published - 2011
Event	21st International Workshop on Combinatorial Algorithms, IWOCA 2010 - London, United Kingdom Duration: Jul 26 2010 → Jul 28 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6460 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Country/Territory	United Kingdom
City	London
Period	7/26/10 → 7/28/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-19222-7_7

Cite this

Kamiński, M., Medvedev, P., & Milanič, M. (2011). Shortest paths between shortest paths and independent sets. In Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, Revised Selected Papers (pp. 56-67). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6460 LNCS). https://doi.org/10.1007/978-3-642-19222-7_7

@inproceedings{b541a7e2186340a5a239f60a027fc81c,

title = "Shortest paths between shortest paths and independent sets",

abstract = "We study problems of reconfiguration of shortest paths in graphs. 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. Moreover, we also study reconfiguration of independent sets in three different models and analyze relationships between these models, observing that shortest path reconfiguration is a special case of independent set reconfiguration in perfect graphs, under any of the three models. Finally, we give polynomial results for restricted classes of graphs (even-hole-free and P4-free graphs).",

author = "Marcin Kami{\'n}ski and Paul Medvedev and Martin Milani{\v c}",

year = "2011",

doi = "10.1007/978-3-642-19222-7_7",

language = "English (US)",

isbn = "9783642192210",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "56--67",

booktitle = "Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, Revised Selected Papers",

}

Kamiński, M, Medvedev, P & Milanič, M 2011, Shortest paths between shortest paths and independent sets. in Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6460 LNCS, pp. 56-67, 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, London, United Kingdom, 7/26/10. https://doi.org/10.1007/978-3-642-19222-7_7

Shortest paths between shortest paths and independent sets. / Kamiński, Marcin; Medvedev, Paul; Milanič, Martin.
Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, Revised Selected Papers. 2011. p. 56-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6460 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Shortest paths between shortest paths and independent sets

AU - Kamiński, Marcin

AU - Medvedev, Paul

AU - Milanič, Martin

PY - 2011

Y1 - 2011

N2 - We study problems of reconfiguration of shortest paths in graphs. 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. Moreover, we also study reconfiguration of independent sets in three different models and analyze relationships between these models, observing that shortest path reconfiguration is a special case of independent set reconfiguration in perfect graphs, under any of the three models. Finally, we give polynomial results for restricted classes of graphs (even-hole-free and P4-free graphs).

AB - We study problems of reconfiguration of shortest paths in graphs. 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. Moreover, we also study reconfiguration of independent sets in three different models and analyze relationships between these models, observing that shortest path reconfiguration is a special case of independent set reconfiguration in perfect graphs, under any of the three models. Finally, we give polynomial results for restricted classes of graphs (even-hole-free and P4-free graphs).

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

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

U2 - 10.1007/978-3-642-19222-7_7

DO - 10.1007/978-3-642-19222-7_7

M3 - Conference contribution

AN - SCOPUS:79953173952

SN - 9783642192210

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 56

EP - 67

BT - Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, Revised Selected Papers

T2 - 21st International Workshop on Combinatorial Algorithms, IWOCA 2010

Y2 - 26 July 2010 through 28 July 2010

ER -

Kamiński M, Medvedev P, Milanič M. Shortest paths between shortest paths and independent sets. In Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, Revised Selected Papers. 2011. p. 56-67. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-19222-7_7

Shortest paths between shortest paths and independent sets

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this