|
2 | added 87 characters in body | ||
|
Edit: apparently I'm linking to a paper that has a different definition of 'switch' The reachability problem is NP-complete for unweighted directed switch graphs. http://www.springerlink.com/content/f2722481747l2170/ This means that in the weighted case it is NP hard to even find switch settings that can reach the target from the starting vertex, let alone reach the target with maximum probability. |
||||
|
|
1 |
|
||
|
The reachability problem is NP-complete for unweighted directed switch graphs. http://www.springerlink.com/content/f2722481747l2170/ This means that in the weighted case it is NP hard to even find switch settings that can reach the target from the starting vertex, let alone reach the target with maximum probability. |
||||
