Thesis Defense :: On the Inverse Shortest Path Length Problem

Primary tabs

The Inverse Shortest Path Length Problem (ISPL) is to find the vector of cost coefficients to satisfy given shortest path length constraints in a network. Given a graph and target shortest path length for some oriin and destination pairs, we want a cost vector such that the shortest path length for each given pair will be equal to its target.

The objective of this dissertation is to explore the complexity, algorithms and applications of the Inverse Shortest Path Length Problem (ISPL). Prior researchers showed that ISPL is NP-complete. We explore the complexity of ISPL for special cases. We also introduce some heuristic algorithms and analyze their worst case performance. We test the algorithms on a set of randomly-generated instances, and observe that te results are usually within 3% of optimality. Finally, we present an application of ISPL to telecommunications bandwidth pricing, and test our heuristics on real-world data.


  • Workflow Status: Published
  • Created By: Barbara Christopher
  • Created: 10/08/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No keywords were submitted.

Target Audience

No target audience selected.