Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5180Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.creator | Karp, Richard M. | - |
| dc.creator | Orlin, James B., 1953- | - |
| dc.date | 2004-05-28T19:26:46Z | - |
| dc.date | 2004-05-28T19:26:46Z | - |
| dc.date | 1980-10 | - |
| dc.date.accessioned | 2013-10-09T02:38:09Z | - |
| dc.date.available | 2013-10-09T02:38:09Z | - |
| dc.date.issued | 2013-10-09 | - |
| dc.identifier | http://hdl.handle.net/1721.1/5180 | - |
| dc.identifier.uri | http://koha.mediu.edu.my:8181/xmlui/handle/1721 | - |
| dc.description | Let G = (V,E) be a digraph with n vertices including a special vertex s. Let E' C E be a designated subset of edges. For each e E E there is an associated real number fl(e). Furthermore, let 1 if e E E' f2(e): 0 if e E-E' The length of edge e is flpe)-Af2(e), where X is a parameter that takes on real values. Thus the length varies additively in X for each edge of E'. We shall present two algorithms for computing the shortest path from s to each vertex v E V parametrically in the parameter X, with respective running times O(n3 ) and O(nlE llogn). For dense digraphs the running time of the former algorithm is comparable to the fastest (non-parametric) shortest path algorithm known. This work generalizes the results of Karp [2] concerning the minimum cycle mean of a digraph, which reduces to the case that E' = E. Furthermore, the second parametric algorithm may be used in conjunction with a transformation given by Bartholdi, Orlin, and Ratliff [1] to give an O(n21logn) algorithm for the cyclic staffing problem. | - |
| dc.format | 880470 bytes | - |
| dc.format | application/pdf | - |
| dc.language | en_US | - |
| dc.publisher | Massachusetts Institute of Technology, Operations Research Center | - |
| dc.relation | Operations Research Center Working Paper;OR 103-80 | - |
| dc.title | Parameter Shortest Path Algorithms with an Application to Cyclic Staffing | - |
| dc.type | Working Paper | - |
| Appears in Collections: | MIT Items | |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.