TY - GEN
T1 - Shortest paths between shortest paths and independent sets
AU - Kamiński, Marcin
AU - Medvedev, Paul
AU - Milanič, Martin
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
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 -