Shortest paths between shortest paths and independent sets

Details Shortest paths between shortest paths and independent sets Shortest paths between shortest paths and independent sets

2010-08-26

arxiv.org/abs/1008.4563v3

Computer Science

Computational Complexity

Scientific paper

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_4$-free graphs).

Affiliated with

Also associated with

No associations

Rating

Shortest paths between shortest paths and independent sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Shortest paths between shortest paths and independent sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shortest paths between shortest paths and independent sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704346