Title:
The Shared Shortest Path Problem in Graphs
Authors:
Jagannatha, Zeal; Peterson, Nicole; Quigley, Sean; Emerick, Brooks; Earl, Christopher; McCulloch, Sean
Publisher:
Denison University
DATE ISSUED:
19-Nov-2011
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/3620; http://hdl.handle.net/2374
Type:
Article
Language:
en_US
Description:
Our research into the Shared Shortest Path Problem (SSPP) attempts to route a number of paths, called journeys, in a graph where journeys share costs of common edges. There are several different ways to view the problem, measured by differing optimum solutions. Our first type of solution attempts to minimize total cost, which is known to be NP-Complete. To satisfy this condition, we used an approach based on the Minimum Spanning Tree. Generally, this approach finds reasonably cost effective solutions, but more effective solutions can be found using other approaches. Our second metric is to treat each journey as an independent agent and attempt to find a Nash Equilibrium (NE) for the graph. From previous research on Congestion Games, we learned that NE always exist for our problem, and created an algorithm that finds them quickly, in practice. Additionally, while attempting to generalize Nash Equilibria, we investigated how Strong Nash Equilibria can also be applied to our problem. While this is one of the more effective optimality conditions, we found that it is likely NP-Complete, both to verify, and to find. In addition, we found that Strong Nash Equilibria do not always exist in graphs. As a result, we chose not to study this approach in detail, but have left it as a field for further study.
Appears in Collections:
Proceedings: 2011 Midstates Conference for Undergraduate Research in Computer Science and Mathematics

Full metadata record

DC FieldValue Language
dc.contributor.authorJagannatha, Zealen
dc.contributor.authorPeterson, Nicoleen
dc.contributor.authorQuigley, Seanen
dc.contributor.authorEmerick, Brooksen
dc.contributor.authorEarl, Christopheren
dc.contributor.authorMcCulloch, Seanen
dc.coverage.spatialUSA - Ohio - Licking - Granvilleen_US
dc.date.accessioned2012-08-20T20:15:11Zen
dc.date.accessioned2013-12-18T22:13:30Z-
dc.date.available2012-08-20T20:15:11Zen
dc.date.available2013-12-18T22:13:30Z-
dc.date.created2011-11-19en
dc.date.issued2011-11-19en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/3620en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionOur research into the Shared Shortest Path Problem (SSPP) attempts to route a number of paths, called journeys, in a graph where journeys share costs of common edges. There are several different ways to view the problem, measured by differing optimum solutions. Our first type of solution attempts to minimize total cost, which is known to be NP-Complete. To satisfy this condition, we used an approach based on the Minimum Spanning Tree. Generally, this approach finds reasonably cost effective solutions, but more effective solutions can be found using other approaches. Our second metric is to treat each journey as an independent agent and attempt to find a Nash Equilibrium (NE) for the graph. From previous research on Congestion Games, we learned that NE always exist for our problem, and created an algorithm that finds them quickly, in practice. Additionally, while attempting to generalize Nash Equilibria, we investigated how Strong Nash Equilibria can also be applied to our problem. While this is one of the more effective optimality conditions, we found that it is likely NP-Complete, both to verify, and to find. In addition, we found that Strong Nash Equilibria do not always exist in graphs. As a result, we chose not to study this approach in detail, but have left it as a field for further study.en_US
dc.language.isoen_USen_US
dc.publisherDenison Universityen_US
dc.relation.ispartofProceedings of the 2011 Midstates Conference on Undergraduate Research in Computer Science and Mathematicsen_US
dc.titleThe Shared Shortest Path Problem in Graphsen_US
dc.typeArticleen_US
dc.contributor.institutionDenison Universityen_US
dc.contributor.repositoryDenison DRCen_US
dc.publisher.digitalDenison Universityen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.