{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T11:27:41Z","timestamp":1750937261451},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2010,8,11]],"date-time":"2010-08-11T00:00:00Z","timestamp":1281484800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s00607-010-0112-1","type":"journal-article","created":{"date-parts":[[2010,8,9]],"date-time":"2010-08-09T21:20:18Z","timestamp":1281388818000},"page":"113-130","source":"Crossref","is-referenced-by-count":1,"title":["Two-level heaps: a new priority queue structure with applications to the single source shortest path problem"],"prefix":"10.1007","volume":"90","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kamesh","family":"Madduri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,8,11]]},"reference":[{"issue":"2","key":"112_CR1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"RK Ahuja","year":"1990","unstructured":"Ahuja RK, Mehlhorn K, Orlin JB, Tarjan RE (1990) Faster algorithms for the shortest path problem. J ACM 37(2): 213\u2013223","journal-title":"J ACM"},{"key":"112_CR2","unstructured":"Brodnik A, Carlsson S, Karlsson J, Ian Munro J (2001) Worst case constant time priority queue. In: Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms (SODA-01), pp 523\u2013528. ACM Press, New York"},{"key":"112_CR3","doi-asserted-by":"crossref","unstructured":"Chakrabarti D, Zhan Y, Faloutsos C (2004) R-MAT: a recursive model for graph mining. In: Proceedings of 4th SIAM international conference on data mining, FL, USA","DOI":"10.1137\/1.9781611972740.43"},{"key":"112_CR4","first-page":"129","volume":"73","author":"BV Cherkassky","year":"1996","unstructured":"Cherkassky BV, Goldberg AV, Radzik T (1996) Shortest paths algorithms: theory and experimental evaluation. Math Program 73: 129\u2013174","journal-title":"Math Program"},{"key":"112_CR5","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, USA"},{"issue":"3","key":"112_CR6","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1109\/34.368194","volume":"17","author":"LA Costa","year":"1995","unstructured":"Costa LA, Geiger D, Gupta A, Vlontozos J (1995) Dynamic programming for detecting, tracking and matching elastic contours. IEEE Trans Pattern Anal Mach Intell 17(3): 294\u2013302","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"112_CR7","doi-asserted-by":"crossref","unstructured":"Cox IJ, Rao SB, Zhong Y (1996) Ration regions: a technique for image segmentation. In: Proceedings of the international conference on pattern recognition, pp 557\u2013564","DOI":"10.1109\/ICPR.1996.546886"},{"key":"112_CR8","unstructured":"Demetrescu C, Goldberg AV, Johnson D (2005) 9th DIMACS implementation challenge: shortest paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"key":"112_CR9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1: 269\u2013271","journal-title":"Numer Math"},{"issue":"6","key":"112_CR10","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson GN (1987) Fast algorithms for shortest paths in planar graphs, with applications. SIAM J Comput 16(6): 1004\u20131022","journal-title":"SIAM J Comput"},{"key":"112_CR11","unstructured":"Goldberg AV (1996) Network optimization library. http:\/\/www.avglab.com\/andrew\/soft.html"},{"key":"112_CR12","doi-asserted-by":"crossref","unstructured":"Goldberg AV (2001) Shortest path algorithms: engineering aspects. In: ISAAC 2001: Proceedings 12th international symposium on algorithms and computation, pp 502\u2013513. Springer, London","DOI":"10.1007\/3-540-45678-3_43"},{"issue":"1","key":"112_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson DB (1977) Efficient algorithms for shortest paths in sparse networks. J ACM 24(1): 1\u201313","journal-title":"J ACM"},{"key":"112_CR14","doi-asserted-by":"crossref","unstructured":"LaMarca A, Ladner RE (1996) The influence of caches on the performance of heaps. ACM JEA 1(4). http:\/\/www.jea.acm.org\/1996\/LaMarcaInfluence\/","DOI":"10.1145\/235141.235145"},{"key":"112_CR15","unstructured":"Meyer U (2001) Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In: Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms (SODA-01), pp 797\u2013806. ACM Press, New York"},{"key":"112_CR16","doi-asserted-by":"crossref","unstructured":"Oberhauser G, Simha R (1995) Fast data structures for shortest path routing: a comparative evaluation. In: Proceedings of IEEE conference communications, vol 95, pp 1597\u20131601, Seattle, WA, June 1995","DOI":"10.1109\/ICC.1995.524471"},{"key":"112_CR17","doi-asserted-by":"crossref","unstructured":"Park J, Penner M, Prasanna VK (2002) Optimizing graph algorithms for improved cache performance. In: Proceedings of international parallel and distributed processing symposium (IPDPS 2002), Fort Lauderdale, FL, April 2002","DOI":"10.1109\/IPDPS.2002.1015509"},{"issue":"2","key":"112_CR18","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G Ramalingam","year":"1996","unstructured":"Ramalingam G, Reps TW (1996) An incremental algorithm for a generalization of the shortest-path problem. J Algorithm 21(2): 267\u2013305","journal-title":"J Algorithm"},{"issue":"1, 2","key":"112_CR19","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0304-3975(95)00079-8","volume":"158","author":"G Ramalingam","year":"1996","unstructured":"Ramalingam G, Reps TW (1996) On the computational complexity of dynamic graph problems. Theor Comput Sci 158(1, 2): 233\u2013277","journal-title":"Theor Comput Sci"},{"key":"112_CR20","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/261342.261352","volume":"28","author":"R Raman","year":"1997","unstructured":"Raman R (1997) Recent results in single-source shortest paths problem. SIGACT News 28: 81\u201387","journal-title":"SIGACT News"},{"key":"112_CR21","doi-asserted-by":"crossref","unstructured":"Raman R (1996) Priority queues: small, monotone and trans-dichotomous. In: ESA, pp 121\u2013137","DOI":"10.1007\/3-540-61680-2_51"},{"key":"112_CR22","doi-asserted-by":"crossref","unstructured":"Sanders P (2000) Fast priority queues for cached memory. ACM JEA 5(7). http:\/\/www.jea.acm.org\/2000\/SandersPriority\/","DOI":"10.1145\/351827.384249"},{"issue":"4","key":"112_CR23","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/j.future.2004.09.001","volume":"21","author":"K Subramani","year":"2005","unstructured":"Subramani K, Kovalchick L (2005) A greedy strategy for detecting negative cost cycles in networks. Future Generat Comput Syst 21(4): 607\u2013623","journal-title":"Future Generat Comput Syst"},{"key":"112_CR24","doi-asserted-by":"crossref","unstructured":"Thorup M (1997) Undirected single source shortest path in linear time. In: Proceedings of the 38th annual symposium on foundations of computer science (FOCS-97), pp 12\u201321. IEEE Computer Society Press, Los Alamitos, October 20\u201322, 1997","DOI":"10.1109\/SFCS.1997.646088"},{"key":"112_CR25","unstructured":"Thorup M (1996) On RAM priority queues. In: Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, SODA\u201996 (Atlanta, Georgia, January 28\u201330, 1996), pp 59\u201367. ACM SIGACT, SIAM, Society for Industrial and Applied Mathematics, Philadelphia, PA"},{"key":"112_CR26","doi-asserted-by":"crossref","unstructured":"Wang C, Ivancic F, Ganai MK, Gupta A (2005) Deciding separation logic formulae by sat and incremental negative cycle elimination. In: LPAR, pp 322\u2013336","DOI":"10.1007\/11591191_23"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-010-0112-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00607-010-0112-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-010-0112-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T10:16:00Z","timestamp":1559384160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00607-010-0112-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,11]]},"references-count":26,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["112"],"URL":"https:\/\/doi.org\/10.1007\/s00607-010-0112-1","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,11]]}}}