|
Shortest shared path problem
|
|
In graph theory, the shared shortest path problem (SSPP) is the problem of routing several journeys though a graph such that the total cost of all journeys is minimized and journeys who share paths split the cost evently among them. History Dr. Sean McCulloch, Professor of Computer Science at Ohio Wesleyan University, started researching the SSPP problem in May 2006, and is currently leading ongoing research into this problem. NP completeness Finding perfect solutions to SSPP is known to be NP-complete, as it is tantamount to searching the set of all possible configurations of states. (The only exception to this is the 2-journey problem, which is polynomial time.) As a result of this, recent research focusses on finding good heuristics to approximate solutions. Nash equilibria A solution to this problem can be approximated by a Nash equilibrium, a state in which none of the journeys can independently change their path to improve their cost. A stronger form of Nash equilibria, strong Nash equilibrium, is a closer approximation of solutions to the problem, but is known to be NP-complete. 
|
| < Prev | Next > |
|---|
Main Menu
| Home |
| Articles |
| Search |
| Submit Article |
| Contact Us |
| Donate to Wikibin |
