{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:49:09Z","timestamp":1740098949747,"version":"3.37.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319671895"},{"type":"electronic","value":"9783319671901"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-67190-1_8","type":"book-chapter","created":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T09:48:49Z","timestamp":1505728129000},"page":"99-113","source":"Crossref","is-referenced-by-count":0,"title":["Improving the Cache-Efficiency of Shortest Path Search"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,19]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"RK Ahuja","year":"1990","unstructured":"Ahuja, R.K., Mehlhorn, K., Orlin, J.B., Tarjan, R.E.: Faster algorithms for the shortest path problem. J. ACM 37(2), 213\u2013223 (1990)","journal-title":"J. ACM"},{"key":"8_CR2","unstructured":"Brodal, G.S.: Worst-case efficient priority queues. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 52\u201358 (1996)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-642-13193-6_36","volume-title":"Experimental Algorithms","author":"A Bruun","year":"2010","unstructured":"Bruun, A., Edelkamp, S., Katajainen, J., Rasmussen, J.: Policy-based benchmarking of weak heaps and their relatives. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 424\u2013435. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13193-6_36"},{"issue":"4","key":"8_CR4","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1111\/0824-7935.00065","volume":"14","author":"JC Culberson","year":"1998","unstructured":"Culberson, J.C., Schaeffer, J.: Pattern databases. Comput. Intell. 14(4), 318\u2013334 (1998)","journal-title":"Comput. Intell."},{"issue":"11","key":"8_CR5","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1145\/363269.363610","volume":"12","author":"RB Dial","year":"1969","unstructured":"Dial, R.B.: Shortest-path forest with topological ordering. Commun. ACM 12(11), 632\u2013633 (1969)","journal-title":"Commun. ACM"},{"key":"8_CR6","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"11","key":"8_CR7","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"JR Driscoll","year":"1988","unstructured":"Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31(11), 1343\u20131354 (1988)","journal-title":"Commun. ACM"},{"key":"8_CR8","unstructured":"Edelkamp, S.: Planning with pattern databases. In: ECP, pp. 13\u201324 (2001)"},{"key":"8_CR9","unstructured":"Edelkamp, S., Schr\u00f6dl, S.: Localizing A*. In: AAAI, pp. 885\u2013890 (2000)"},{"issue":"1","key":"8_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.3233\/FI-2014-1003","volume":"131","author":"S Evangelista","year":"2014","unstructured":"Evangelista, S., Kristensen, L.M.: A sweep-line method for B\u00fcchi automata-based model checking. Fundam. Inform. 131(1), 27\u201353 (2014)","journal-title":"Fundam. Inform."},{"issue":"12","key":"8_CR11","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"RW Floyd","year":"1964","unstructured":"Floyd, R.W.: Algorithm 245: treesort 3. Commun. ACM 7(12), 701 (1964)","journal-title":"Commun. ACM"},{"issue":"1","key":"8_CR12","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"ML Fredman","year":"1986","unstructured":"Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: a new form of self-adjusting heap. Algorithmica 1(1), 111\u2013129 (1986)","journal-title":"Algorithmica"},{"issue":"3","key":"8_CR13","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithm. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Geisberger, R., Schieferdecker, D.: Heuristic contraction hierarchies with approximation guarantee. In: SOCS, pp. 31\u201338 (2010)","DOI":"10.1609\/socs.v1i1.18161"},{"key":"8_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-2217(02)00915-3","volume":"151","author":"G Ghiani","year":"2003","unstructured":"Ghiani, G., Guerriero, F., Laporte, G., Musmanno, R.: Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. Eur. J. Oper. Res. 151, 1\u201311 (2003)","journal-title":"Eur. J. Oper. Res."},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for heuristic determination of minimum path cost. IEEE Trans. Syst. Sci. Cybern. 4, 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"8_CR17","volume-title":"Fundamentals of Data Structures in C","author":"E Horowitz","year":"2007","unstructured":"Horowitz, E., Sahni, S., Anderson-Freed, S.: Fundamentals of Data Structures in C, 2nd edn. Silicon Press, Summit (2007)","edition":"2"},{"key":"8_CR18","unstructured":"Kaplan, H., Tarjan, R.E., Zwick, U.: Fibonacci heaps revisited, pp. 187\u2013205 (2014). arXiv:1407.5750v1"},{"issue":"1","key":"8_CR19","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"P Klein","year":"1997","unstructured":"Klein, P., Rao, S., Rauch, M., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR20","unstructured":"Korf, R.E.: Finding optimal solutions to Rubik\u2019s Cube using pattern databases. In: AAAI, pp. 700\u2013705 (1997)"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Kristensen, L., Mailund, T.: Path finding with the sweep-line method using external storage. In: ICFEM, pp. 319\u2013337 (2003)","DOI":"10.1007\/978-3-540-39893-6_19"},{"issue":"1","key":"8_CR22","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/jagm.1998.0985","volume":"31","author":"A LaMarca","year":"1999","unstructured":"LaMarca, A., Ladner, R.E.: The influence of caches on the performance of sorting. J. Algorithms 31(1), 66\u2013104 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"8_CR23","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TCIAIG.2013.2263884","volume":"6","author":"DP Liebana","year":"2014","unstructured":"Liebana, D.P., Powley, E.J., Whitehouse, D., Rohlfshagen, P., Samothrakis, S., Cowling, P.I., Lucas, S.M.: Solving the physical traveling salesman problem: tree search and macro actions. IEEE Trans. Comput. Intell. AI Games 6(1), 31\u201345 (2014)","journal-title":"IEEE Trans. Comput. Intell. AI Games"},{"issue":"3","key":"8_CR24","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1145\/965139.807380","volume":"12","author":"H Lieberman","year":"1978","unstructured":"Lieberman, H.: How to color in a coloring book. SIGGRAPH Comput. Graph. 12(3), 111\u2013116 (1978)","journal-title":"SIGGRAPH Comput. Graph."},{"key":"8_CR25","unstructured":"Otte, M.: On solving floating point SSSP using an integer priority queue. CoRR, abs\/1606.00726 (2016)"},{"key":"8_CR26","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/351827.384249","volume":"5","author":"P Sanders","year":"2000","unstructured":"Sanders, P.: Fast priority queues for cached memory. ACM J. Exp. Algorithmics 5, 7 (2000)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"3","key":"8_CR27","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1145\/214748.214759","volume":"30","author":"JT Stasko","year":"1987","unstructured":"Stasko, J.T., Vitter, J.S.: Pairing heaps: experiments and analysis. Commun. ACM 30(3), 234\u2013249 (1987)","journal-title":"Commun. ACM"},{"issue":"3","key":"8_CR28","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1609\/aimag.v35i3.2547","volume":"35","author":"NR Sturtevant","year":"2014","unstructured":"Sturtevant, N.R.: The grid-based path planning competition. AI Mag. 35(3), 66\u201369 (2014)","journal-title":"AI Mag."},{"key":"8_CR29","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46, 362\u2013394 (1999)","journal-title":"J. ACM"},{"key":"8_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"776","DOI":"10.1007\/978-3-540-39658-1_69","volume-title":"Algorithms - ESA 2003","author":"D Wagner","year":"2003","unstructured":"Wagner, D., Willhalm, T.: Geometric speed-up techniques for finding shortest paths in large sparse graphs. In: Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 776\u2013787. Springer, Heidelberg (2003). doi: 10.1007\/978-3-540-39658-1_69"},{"issue":"6","key":"8_CR31","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"JWJ Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: heapsort. Commun. ACM 7(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","KI 2017: Advances in Artificial Intelligence"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67190-1_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T00:13:06Z","timestamp":1693008786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67190-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319671895","9783319671901"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67190-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}