{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:21:08Z","timestamp":1725603668845},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_37","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"433-444","source":"Crossref","is-referenced-by-count":2,"title":["An Experimental Study on Approximating K Shortest Simple Paths"],"prefix":"10.1007","author":[{"given":"Asaf","family":"Frieder","sequence":"first","affiliation":[]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"37_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput.\u00a028(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Bernstein, A.: A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In: Proc. of 21st SODA, pp. 742\u2013755 (2010)","DOI":"10.1137\/1.9781611973075.61"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Brander, A.W., Sinclair, M.C.: A comparative study of k-shortest path algorithms. In: Proc. 11th UK Performance Engineering Worksh. for Computer and Telecommunications Systems (September 1995)","DOI":"10.1007\/978-1-4471-1007-1_25"},{"issue":"5","key":"37_CR4","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/S0097539705429847","volume":"37","author":"C. Demetrescu","year":"2008","unstructured":"Demetrescu, C., Thorup, M., Chowdhury, R., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Comput.\u00a037(5), 1299\u20131318 (2008)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"37_CR5","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput.\u00a029(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"37_CR6","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D. Eppstein","year":"1998","unstructured":"Eppstein, D.: Finding the k shortest paths. SIAM Journal on Computing\u00a028(2), 652\u2013673 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"7","key":"37_CR7","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/j.ipl.2008.12.015","volume":"109","author":"Z. Gotthilf","year":"2009","unstructured":"Gotthilf, Z., Lewenstein, M.: Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett.\u00a0109(7), 352\u2013355 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"37_CR8","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":"Hadjiconstantinou, E., Christofides, N.: An efficient implementation of an algorithm for finding K shortest simple paths. Networks\u00a034(2), 88\u2013101 (1999)","journal-title":"Networks"},{"key":"37_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/1290672.1290682","volume":"3","author":"J. Hershberger","year":"2007","unstructured":"Hershberger, J., Maxel, M., Suri, S.: Finding the k shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms\u00a03, 45 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proc. of 42nd FOCS, pp. 252\u2013259 (2001)","DOI":"10.1109\/SFCS.2001.959899"},{"issue":"4","key":"37_CR11","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1002\/net.3230120406","volume":"12","author":"N. Katoh","year":"1982","unstructured":"Katoh, N., Ibaraki, T., Mine, H.: An efficient algorithm for K shortest simple paths. Networks\u00a012(4), 411\u2013427 (1982)","journal-title":"Networks"},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1287\/mnsc.18.7.401","volume":"18","author":"E.L. Lawler","year":"1971","unstructured":"Lawler, E.L.: A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Management Science\u00a018, 401\u2013405 (1971\/1972)","journal-title":"Management Science"},{"issue":"3","key":"37_CR13","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1142\/S0129054199000186","volume":"10","author":"E. Martins","year":"1999","unstructured":"Martins, E., Pascoal, M., Esteves dos Santos, J.: Deviation algorithms for ranking shortest paths. Int. J. Found. Comp. Sci.\u00a010(3), 247\u2013263 (1999)","journal-title":"Int. J. Found. Comp. Sci."},{"key":"37_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1002\/net.3230160204","volume":"16","author":"A. Perko","year":"1986","unstructured":"Perko, A.: Implementation of algorithms for K shortest loopless paths. Networks\u00a016, 149\u2013160 (1986)","journal-title":"Networks"},{"key":"37_CR15","doi-asserted-by":"crossref","unstructured":"Roditty, L.: On the k shortest simple paths problem in weighted directed graphs. SIAM Journal on Computing, 2363\u20132376 (2010)","DOI":"10.1137\/080730950"},{"key":"37_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/11523468_21","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Zwick, U.: Replacement paths and k simple shortest paths in unweighted directed graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 249\u2013260. Springer, Heidelberg (2005)"},{"key":"37_CR17","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: Proc. FOCS (2010)","DOI":"10.1109\/FOCS.2010.67"},{"key":"37_CR18","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: Faster replacement paths. In: Proc. of 22th SODA (2011)","DOI":"10.1137\/1.9781611973082.102"},{"key":"37_CR19","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"J.Y. Yen","year":"1970","unstructured":"Yen, J.Y.: Finding the K shortest loopless paths in a network. Management Science\u00a017, 712\u2013716 (1970\/1971)","journal-title":"Management Science"},{"issue":"3","key":"37_CR20","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U. Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. JACM\u00a049(3), 289\u2013317 (2002)","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T12:08:35Z","timestamp":1560514115000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}