{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:33Z","timestamp":1725551133171},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_31","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:04Z","timestamp":1269882724000},"page":"343-354","source":"Crossref","is-referenced-by-count":10,"title":["On the Difficulty of Some Shortest Path Problems"],"prefix":"10.1007","author":[{"given":"John","family":"Hershberger","sequence":"first","affiliation":[]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[]},{"given":"Amit","family":"Bhosle","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"31_CR1","unstructured":"N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problem. In 32nd Symposium on Foundations of Computer Science, 569\u2013575, 1991."},{"key":"31_CR2","unstructured":"A. Archer. Private communication, 2001."},{"key":"31_CR3","unstructured":"A. Archer and E. Tardos. Frugal path mechanisms. In Proc. 13th Annual ACMSIAM Symposium on Discrete Algorithms, pages 991\u2013999, 2002."},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0167-6377(89)90003-5","volume":"8","author":"M. O. Ball","year":"1989","unstructured":"M. O. Ball, B. L. Golden, and R. V. Vohra. Finding the most vital arcs in a network. Oper. Res. Letters, 8:73\u201376, 1989.","journal-title":"Oper. Res. Letters"},{"key":"31_CR5","series-title":"Technical Report","volume-title":"The complexity of finding most vital arcs and nodes","author":"A. Bar-Noy","year":"1995","unstructured":"A. Bar-Noy, S. Khuller, and B. Schieber. The complexity of finding most vital arcs and nodes. Technical Report CS-TR-3539, Institute for Advanced Studies, University of Maryland, College Park, MD, 1995."},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"A. Brander and M. Sinclair. A comparative study of K-shortest path algorithms. In Proc. of 11th UK Performance Engineering Workshop, pages 370\u2013379, 1995.","DOI":"10.1007\/978-1-4471-1007-1_25"},{"issue":"2","key":"31_CR7","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D. Eppstein","year":"1998","unstructured":"D. Eppstein. Finding the k shortest paths. SIAM J. Computing, 28(2):652\u2013673, 1998.","journal-title":"SIAM J. Computing"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In INFOCOM, pages 519\u2013528, 2000.","DOI":"10.1109\/INFCOM.2000.832225"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M. Fredman","year":"1976","unstructured":"M. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. of Computing, 5:83\u201389, 1976.","journal-title":"SIAM J. of Computing"},{"issue":"2","key":"31_CR10","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<88::AID-NET2>3.0.CO;2-1","volume":"34","author":"E. Hadjiconstantinou","year":"1999","unstructured":"E. Hadjiconstantinou and N. Christofides. An efficient implementation of an algorithm for finding K shortest simple paths. Networks, 34(2):88\u2013101, September 1999.","journal-title":"Networks"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"J. Hershberger and S. Suri. Vickrey prices and shortest paths: What is an edge worth? In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 252\u2013259, 2001.","DOI":"10.1109\/SFCS.2001.959899"},{"key":"31_CR12","unstructured":"J. Hershberger, M. Maxel, and S. Suri. Finding the k Shortest Simple Paths: A New Algorithm and its Implementation. To appear in Proc. of ALENEX, 2003."},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.1137\/0222071","volume":"22","author":"D. R. Karger","year":"1993","unstructured":"D. R. Karger, D. Koller, and S. J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM J. Comput., 22:1199\u20131217, 1993.","journal-title":"SIAM J. Comput."},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1002\/net.3230120406","volume":"12","author":"N. Katoh","year":"1982","unstructured":"N. Katoh, T. Ibaraki, and H. Mine. An efficient algorithm for k shortest simple paths. Networks, 12:411\u2013427, 1982.","journal-title":"Networks"},{"issue":"3","key":"31_CR15","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","volume":"28","author":"D. Kirkpatrick","year":"1984","unstructured":"D. Kirkpatrick and S. Reisch. Upper bounds for sorting integers on random access machines. Theoretical Computer Science, 28(3):263\u2013276, 1984.","journal-title":"Theoretical Computer Science"},{"key":"31_CR16","doi-asserted-by":"crossref","unstructured":"E. L. Lawler. A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, pages 401\u2013405, 1972.","DOI":"10.1287\/mnsc.18.7.401"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0167-6377(89)90065-5","volume":"8","author":"K. Malik","year":"1989","unstructured":"K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path problem. Oper. Res. Letters, 8:223\u2013227, 1989.","journal-title":"Oper. Res. Letters"},{"key":"31_CR18","volume-title":"A new implementation of Yen\u2019s ranking loopless paths algorithm","author":"E. Martins","year":"2000","unstructured":"E. Martins and M. Pascoal. A new implementation of Yen\u2019s ranking loopless paths algorithm. Submited for publication, Universidade de Coimbra, Portugal, 2000."},{"key":"31_CR19","series-title":"Technical report","volume-title":"A new algorithm for ranking loopless paths","author":"E. Martins","year":"1997","unstructured":"E. Martins, M. Pascoal, and J. Santos. A new algorithm for ranking loopless paths. Technical report, Universidade de Coimbra, Portugal, 1997."},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"E. Nardelli, G. Proietti, and P. Widmayer. Finding the most vital node of a shortest path. In Proc. COCOON, 2001.","DOI":"10.1007\/3-540-44679-6_31"},{"key":"31_CR21","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ronen. Algorithmic mechanism design. In Proc. 31st Annu. ACM Sympos. Theory Comput., 1999.","DOI":"10.1145\/301250.301287"},{"key":"31_CR22","unstructured":"W. J. Paul and J. Simon. Decision trees and random access machines. In Proc. International Symp. on Logic and Algorithmic, pages 331\u2013340, 1980."},{"key":"31_CR23","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1002\/net.3230160204","volume":"16","author":"A. Perko","year":"1986","unstructured":"A. Perko. Implementation of algorithms for K shortest loopless paths. Networks, 16:149\u2013160, 1986.","journal-title":"Networks"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"J. Y. Yen","year":"1971","unstructured":"J. Y. Yen. Finding the K shortest loopless paths in a network. Management Science, 17:712\u2013716, 1971.","journal-title":"Management Science"},{"key":"31_CR25","unstructured":"J. Y. Yen. Another algorithm for finding the K shortest loopless network paths. In Proc. of 41st Mtg. Operations Research Society of America, volume 20, 1972."},{"key":"31_CR26","unstructured":"U. Zwick. All Pairs Shortest Paths inWeighted Directed Graphs-exact and almost exact algorithms. In Proc. IEEE Symposium on Foundations of Computer Science, 310\u2013319, 1998."},{"key":"31_CR27","unstructured":"U. Zwick. All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication. In Electronic Colloquium on Computational Complexity, 2000."}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T15:02:11Z","timestamp":1558969331000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}