{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T17:03:22Z","timestamp":1743008602129,"version":"3.40.3"},"publisher-location":"Cham","reference-count":98,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319494869"},{"type":"electronic","value":"9783319494876"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-49487-6_6","type":"book-chapter","created":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T14:11:38Z","timestamp":1478787098000},"page":"185-225","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["External-Memory State Space Search"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,11]]},"reference":[{"issue":"9","key":"6_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. J. ACM 31(9), 1116\u20131127 (1988)","journal-title":"J. ACM"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Ajwani, D., Dementiev, R., Meyer, U.: A computational study of external-memory BFS algorithms. In: SODA, pp. 601\u2013610 (2006)","DOI":"10.1145\/1109557.1109623"},{"key":"6_CR3","unstructured":"Ajwani, D., Malinger, I., Meyer, U., Toledo, S.: Graph search on flash memory. MPI-TR (2008)"},{"key":"6_CR4","volume-title":"The Complete Book of CONNECT 4: History, Strategy, Puzzles","author":"JD Allen","year":"2011","unstructured":"Allen, J.D.: The Complete Book of CONNECT 4: History, Strategy, Puzzles. Sterling Publishing, New York (2011)"},{"key":"6_CR5","unstructured":"Allis, L.V.: A knowledge-based approach to connect-four. The game is solved: white wins. Master\u2019s thesis, Vrije Univeriteit, The Netherlands (1998)"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-642-03240-0_14","volume-title":"Formal Methods for Industrial Critical Systems","author":"J Barnat","year":"2009","unstructured":"Barnat, J., Brim, L., Edelkamp, S., Sulewski, D., \u0160ime\u010dek, P.: Can flash memory help in model checking? In: Cofer, D., Fantechi, A. (eds.) FMICS 2008. LNCS, vol. 5596, pp. 150\u2013165. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-03240-0_14"},{"issue":"1","key":"6_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0004-3702(94)00011-O","volume":"72","author":"A Barto","year":"1995","unstructured":"Barto, A., Bradtke, S., Singh, S.: Learning to act using real-time dynamic programming. Artif. Intell. 72(1), 81\u2013138 (1995)","journal-title":"Artif. Intell."},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Bloem, R., Ravi, K., Somenzi, F.: Symbolic guided search for CTL model checking. In: DAC, pp. 29\u201334 (2000)","DOI":"10.1145\/337292.337306"},{"key":"6_CR9","unstructured":"Bonet, B.: Efficient algorithms to rank and unrank permutations in lexicographic order. In: AAAI-Workshop on Search in AI and Robotics (2008)"},{"key":"6_CR10","unstructured":"Bonet, B., Geffner, H.: Learning depth-first: a unified approach to heuristic search in deterministic and non-deterministic settings, and its application to MDPs. In: ICAPS, pp. 142\u2013151 (2006)"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-642-02652-2_7","volume-title":"Model Checking Software","author":"D Bo\u0161na\u010dki","year":"2009","unstructured":"Bo\u0161na\u010dki, D., Edelkamp, S., Sulewski, D.: Efficient probabilistic model checking on general purpose graphics processors. In: P\u0103s\u0103reanu, C.S. (ed.) SPIN 2009. LNCS, vol. 5578, pp. 32\u201349. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02652-2_7"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Botelho, F.C., Pagh, R., Ziviani, N.: Simple and space-efficient minimal perfect hash functions. In: WADS, pp. 139\u2013150 (2007)","DOI":"10.1007\/978-3-540-73951-7_13"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Botelho, F.C., Ziviani, N.: External perfect hashing for very large key sets. In: CIKM, pp. 653\u2013662 (2007)","DOI":"10.1145\/1321440.1321532"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Breyer, T.M., Korf, R.E.: 1.6-bit pattern databases. In: AAAI (2010)","DOI":"10.1609\/aaai.v24i1.7558"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Burns, E., Lemons, S., Ruml, W., Zhou, R.: Suboptimal and anytime heuristic search on multi-core machines. In: ICAPS (2009)","DOI":"10.1613\/jair.3094"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Burns, E., Lemons, S., Zhou, R., Ruml, W.: Best-first heuristic search for multi-core machines. In: IJCAI, pp. 449\u2013455 (2009)","DOI":"10.1609\/icaps.v19i1.13375"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Cazenave, T.: Nested monte-carlo search. In: IJCAI, pp. 456\u2013461 (2009)","DOI":"10.1109\/IPDPS.2009.5161122"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Cederman, D., Tsigas, P.: A practical quicksort algorithm for graphics processors. Technical report 2008\u201301, Chalmers University of Technology (2008)","DOI":"10.1007\/978-3-540-87744-8_21"},{"key":"6_CR19","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"1990","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. MIT Press, Cambridge (1990)"},{"issue":"4","key":"6_CR20","doi-asserted-by":"publisher","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."},{"key":"6_CR21","unstructured":"Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. In: OSDI (USENIX Association, Berkeley, CA, USA) (2004)"},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Karlin, A., Mehlhorn, K., auf der Heide, F.M., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing upper and lower bounds. SIAM J. Comput. 23, 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"D\u00f6bbelin, R., Sch\u00fctt, T., Reinefeld, A.: Building large compressed PDBs for the sliding tile puzzle. In: Computer Games, pp. 16\u201327 (2013)","DOI":"10.1007\/978-3-319-05428-5_2"},{"key":"6_CR24","unstructured":"Edelkamp, S.: Planning with pattern databases. In: ECP, pp. 13\u201324 (2001). Reprint 2013 by AAAI Press. http:\/\/www.aaai.org\/ocs\/index.php\/ECP\/ECP01"},{"key":"6_CR25","unstructured":"Edelkamp, S.: External symbolic heuristic search with pattern databases. In: ICAPS, pp. 51\u201360 (2005)"},{"key":"6_CR26","unstructured":"Edelkamp, S., Jabbar, S.: Externalizing real-time model checking. In: MOCHART, pp. 67\u201383 (2006)"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11691617_1","volume-title":"Model Checking Software","author":"S Edelkamp","year":"2006","unstructured":"Edelkamp, S., Jabbar, S.: Large-scale directed model checking LTL. In: Valmari, A. (ed.) SPIN 2006. LNCS, vol. 3925, pp. 1\u201318. Springer, Heidelberg (2006). doi: 10.1007\/11691617_1"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Jabbar, S., Bonet, B.: External memory value iteration. In: ICAPS, pp. 414\u2013429 (2007)","DOI":"10.1007\/11841883_29"},{"key":"6_CR29","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/978-3-540-30221-6_18","volume-title":"KI 2004: Advances in Artificial Intelligence","author":"S Edelkamp","year":"2004","unstructured":"Edelkamp, S., Jabbar, S., Schr\u00f6dl, S.: External A*. In: Biundo, S., Fr\u00fchwirth, T., Palm, G. (eds.) KI 2004. LNCS (LNAI), vol. 3238, pp. 226\u2013240. Springer, Heidelberg (2004). doi: 10.1007\/978-3-540-30221-6_18"},{"key":"6_CR30","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-540-74565-5_36","volume-title":"KI 2007: Advances in Artificial Intelligence","author":"S Edelkamp","year":"2007","unstructured":"Edelkamp, S., Kissmann, P.: Externalizing the multiple sequence alignment problem with affine gap costs. In: Hertzberg, J., Beetz, M., Englert, R. (eds.) KI 2007. LNCS (LNAI), vol. 4667, pp. 444\u2013447. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-74565-5_36"},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-540-85845-4_23","volume-title":"KI 2008: Advances in Artificial Intelligence","author":"S Edelkamp","year":"2008","unstructured":"Edelkamp, S., Kissmann, P.: Symbolic classification of general two-player games. In: Dengel, A.R., Berns, K., Breuel, T.M., Bomarius, F., Roth-Berghofer, T.R. (eds.) KI 2008. LNCS (LNAI), vol. 5243, pp. 185\u2013192. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-85845-4_23"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Kissmann, P., Jabbar, S.: Scaling search with pattern databases. In: MOCHART, pp. 49\u201364 (2008)","DOI":"10.1007\/978-3-642-00431-5_4"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Kissmann, P., Rohte, M.: Symbolic and explicit search hybrid through perfect hash functions - a case study in connect four. In: ICAPS (2014)","DOI":"10.1609\/icaps.v24i1.13637"},{"issue":"2\u20133","key":"6_CR34","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s10009-002-0104-3","volume":"5","author":"S Edelkamp","year":"2004","unstructured":"Edelkamp, S., Leue, S., Lluch-Lafuente, A.: Directed explicit-state model checking in the validation of communication protocols. Int. J. Softw. Tools Technol. 5(2\u20133), 247\u2013267 (2004)","journal-title":"Int. J. Softw. Tools Technol."},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Sanders, P., Simecek, P.: Semi-external LTL model checking. In: CAV, pp. 530\u2013542 (2008)","DOI":"10.1007\/978-3-540-70545-1_50"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Sulewski, D.: Flash-efficient LTL model checking with minimal counterexamples. In: SEFM, pp. 73\u201382 (2008)","DOI":"10.1109\/SEFM.2008.34"},{"key":"6_CR37","unstructured":"Edelkamp, S., Sulewski, D.: Model checking via delayed duplicate detection on the GPU. Technical report 821, TU Dortmund (2008)"},{"key":"6_CR38","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Sulewski, D.: Efficient probabilistic model checking on general purpose graphics processors. In: SPIN (2010)","DOI":"10.1007\/978-3-642-16164-3_8"},{"key":"6_CR39","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Sulewski, D.: GPU exploration of two-player games with perfect hash functions. In: SOCS (2010)","DOI":"10.1609\/socs.v1i1.18167"},{"key":"6_CR40","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Sulewski, D.: External memory breadth-first search with delayed duplicate detection on the GPU. In: MOCHART, pp. 12\u201331 (2011)","DOI":"10.1007\/978-3-642-20674-0_2"},{"key":"6_CR41","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Sulewski, D., Y\u00fccel, C.: Perfect hashing for state space exploration on the GPU. In: ICAPS, pp. 57\u201364 (2010)","DOI":"10.1609\/icaps.v20i1.13414"},{"key":"6_CR42","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Tang, Z.: Monte-carlo tree search for the multiple sequence alignment problem. In: SOCS, pp. 9\u201317 (2015)","DOI":"10.1609\/socs.v6i1.18359"},{"key":"6_CR43","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"3","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $$o(1)$$ worst case access time. J. ACM 3, 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"6_CR44","doi-asserted-by":"crossref","unstructured":"Govindaraju, N.K., Gray, J., Kumar, R., Manocha, D.: GPUTeraSort: high performance graphics coprocessor sorting for large database management. In: SIGMOD, pp. 325\u2013336 (2006)","DOI":"10.1145\/1142473.1142511"},{"key":"6_CR45","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0004-3702(01)00106-0","volume":"129","author":"E Hansen","year":"2001","unstructured":"Hansen, E., Zilberstein, S.: LAO*: a heuristic search algorithm that finds solutions with loops. Artif. Intell. 129, 35\u201362 (2001)","journal-title":"Artif. Intell."},{"key":"6_CR46","first-page":"851","volume-title":"GPU Gems 3","author":"M Harris","year":"2007","unstructured":"Harris, M., Sengupta, S., Owens, J.D.: Parallel prefix sum (scan) with CUDA. In: Nguyen, H. (ed.) GPU Gems 3, pp. 851\u2013876. Addison-Wesley, Salt Lake City (2007)"},{"issue":"2","key":"6_CR47","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"N Hart","year":"1968","unstructured":"Hart, N., Nilsson, J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"6_CR48","unstructured":"Helmert, M.: Decidability and undecidability results for planning with numerical state variables. In: AIPS, pp. 303\u2013312 (2002)"},{"key":"6_CR49","doi-asserted-by":"crossref","unstructured":"Helmert, M., Domshlak, C.: Landmarks, critical paths, abstractions: what\u2019s the difference anyway? In: ICAPS (2009)","DOI":"10.1609\/icaps.v19i1.13370"},{"key":"6_CR50","unstructured":"Helmert, M., Haslum, P., Hoffmann, J.: Flexible abstraction heuristics for optimal sequential planning. In: ICAPS, pp. 176\u2013183 (2007)"},{"issue":"7","key":"6_CR51","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 64: quicksort. Commun. ACM 4(7), 321 (1961)","journal-title":"Commun. ACM"},{"key":"6_CR52","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1613\/jair.1144","volume":"20","author":"J Hoffmann","year":"2003","unstructured":"Hoffmann, J.: The metric FF planning system: translating \u201cIgnoring the delete list\u201d to numerical state variables. J. Artif. Intell. Res. 20, 291\u2013341 (2003)","journal-title":"J. Artif. Intell. Res."},{"key":"6_CR53","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1613\/jair.855","volume":"14","author":"J Hoffmann","year":"2001","unstructured":"Hoffmann, J., Nebel, B.: Fast plan generation through heuristic search. J. Artif. Intell. Res. 14, 253\u2013302 (2001)","journal-title":"J. Artif. Intell. Res."},{"key":"6_CR54","unstructured":"Jabbar, S.: External memory algorithms for state space exploration in model checking and action planning. PhD thesis, TU Dortmund (2008)"},{"key":"6_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-540-30579-8_21","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"S Jabbar","year":"2005","unstructured":"Jabbar, S., Edelkamp, S.: I\/O efficient directed model checking. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol. 3385, pp. 313\u2013329. Springer, Heidelberg (2005). doi: 10.1007\/978-3-540-30579-8_21"},{"key":"6_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/11609773_16","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"S Jabbar","year":"2005","unstructured":"Jabbar, S., Edelkamp, S.: Parallel external directed model checking with linear I\/O. In: Emerson, E.A., Namjoshi, K.S. (eds.) VMCAI 2006. LNCS, vol. 3855, pp. 237\u2013251. Springer, Heidelberg (2005). doi: 10.1007\/11609773_16"},{"issue":"6","key":"6_CR57","first-page":"164 903","volume":"124","author":"G Jaychandran","year":"2006","unstructured":"Jaychandran, G., Vishal, V., Pande, V.S.: Using massively parallel simulations, Markovian models to study protein folding: examining the Villin head-piece. J. Chem. Phys. 124(6), 164 903\u2013164 914 (2006)","journal-title":"J. Chem. Phys."},{"key":"6_CR58","doi-asserted-by":"crossref","unstructured":"Kishimoto, A., Fukunaga, A., Botea, A.: On the scaling behavior of HDA*. In: SOCS (2010)","DOI":"10.1609\/socs.v1i1.18163"},{"key":"6_CR59","doi-asserted-by":"crossref","unstructured":"Kishimoto, A., Fukunaga, A.S., Botea, A.: Scalable, parallel best-first search for optimal sequential planning. In: ICAPS (2009)","DOI":"10.1609\/icaps.v19i1.13350"},{"key":"6_CR60","doi-asserted-by":"crossref","unstructured":"Kocsis, L., Szepesv\u00e1ri, C.: Bandit based Monte-Carlo planning. In: ICML, pp. 282\u2013293 (2006)","DOI":"10.1007\/11871842_29"},{"issue":"1","key":"6_CR61","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0004-3702(93)90045-D","volume":"62","author":"RE Korf","year":"1993","unstructured":"Korf, R.E.: Linear-space best-first search. Artif. Intell. 62(1), 41\u201378 (1993)","journal-title":"Artif. Intell."},{"key":"6_CR62","unstructured":"Korf, R.E.: Finding optimal solutions to Rubik\u2019s cube using pattern databases. In: AAAI, pp. 700\u2013705 (1997)"},{"key":"6_CR63","unstructured":"Korf, R.E.:. Breadth-first frontier search with delayed duplicate detection. In: MOCHART, pp. 87\u201392 (2003)"},{"key":"6_CR64","unstructured":"Korf, R.E.: Best-first frontier search with delayed duplicate detection. In: AAAI, pp. 650\u2013657 (2004)"},{"key":"6_CR65","unstructured":"Korf, R.E.: Minimizing disk I\/O in two-bit breadth-first search. In: AAAI, pp. 317\u2013324 (2008)"},{"key":"6_CR66","unstructured":"Korf, R.E., Felner, A.: Disjoint pattern database heuristics. In: Chips Challenging Champions: Games, Computers and Artificial Intelligence, pp. 13\u201326. Elsevier (2002)"},{"key":"6_CR67","unstructured":"Korf, R.E., Felner, A.: Recent progress in heuristic search: a case study of the four-peg towers of Hanoi problem. In: IJCAI, pp. 2324\u20132329 (2007)"},{"key":"6_CR68","unstructured":"Korf, R.E., Schultze, T.: Large-scale parallel breadth-first search. In: AAAI, pp. 1380\u20131385 (2005)"},{"key":"6_CR69","unstructured":"Korf, R.E., Zhang, W.: Divide-and-conquer frontier search applied to optimal sequence alignment. In: AAAI, pp. 910\u2013916 (2000)"},{"issue":"5","key":"6_CR70","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1145\/1089023.1089024","volume":"52","author":"RE Korf","year":"2005","unstructured":"Korf, R.E., Zhang, W., Thayer, I., Hohwald, H.: Frontier search. J. ACM 52(5), 715\u2013748 (2005)","journal-title":"J. ACM"},{"key":"6_CR71","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":"3","key":"6_CR72","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1145\/882262.882363","volume":"22","author":"J Krueger","year":"2003","unstructured":"Krueger, J., Westermann, R.: Linear algebra operators for GPU implementation of numerical algorithms. ACM Trans. Graph. 22(3), 908\u2013916 (2003)","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"6_CR73","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1330311.1330319","volume":"51","author":"D Kunkle","year":"2008","unstructured":"Kunkle, D., Cooperman, G.: Solving Rubik\u2019s cube: disk is the new RAM. Commun. ACM 51(4), 31\u201333 (2008)","journal-title":"Commun. ACM"},{"key":"6_CR74","doi-asserted-by":"crossref","unstructured":"Kupferschmid, S., Dr\u00e4ger, K., Hoffmann, J., Finkbeiner, B., Dierks, H., Podelski, A., Behrmann, G.: Uppaal\/DMC - abstraction-based Heuristics for directed model checking. In: TACAS, pp. 679\u2013682 (2007)","DOI":"10.1007\/978-3-540-71209-1_52"},{"key":"6_CR75","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-540-75520-3_18","volume-title":"Algorithms \u2013 ESA 2007","author":"M Mare\u0161","year":"2007","unstructured":"Mare\u0161, M., Straka, M.: Linear-time ranking of permutations. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 187\u2013193. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-75520-3_18"},{"key":"6_CR76","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/3-540-45749-6_63","volume-title":"Algorithms \u2014 ESA 2002","author":"K Mehlhorn","year":"2002","unstructured":"Mehlhorn, K., Meyer, U.: External-memory breadth-first search with sublinear I\/O. In: M\u00f6hring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 723\u2013735. Springer, Heidelberg (2002). doi: 10.1007\/3-540-45749-6_63"},{"key":"6_CR77","unstructured":"Munagala, K., Ranade, A.: I\/O-complexity of graph algorithms. In: SODA, pp. 687\u2013694 (1999)"},{"issue":"6","key":"6_CR78","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0020-0190(01)00141-7","volume":"79","author":"W Myrvold","year":"2001","unstructured":"Myrvold, W., Ruskey, F.: Ranking and unranking permutations in linear time. Inf. Process. Lett. 79(6), 281\u2013284 (2001)","journal-title":"Inf. Process. Lett."},{"key":"6_CR79","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1002\/jcc.20289","volume":"26","author":"JC Phillips","year":"2005","unstructured":"Phillips, J.C., Braun, R., Wang, W., Gumbart, J., Tajkhorshid, E., Villa, E., Chipot, C., Skeel, R.D., Kale, L., Schulten, K.: Scalable molecular dynamics with NAMD. J. Comp. Chem. 26, 1781\u20131802 (2005)","journal-title":"J. Comp. Chem."},{"key":"6_CR80","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-642-12659-8_24","volume-title":"High Performance Computing Systems and Applications","author":"A Reinefeld","year":"2010","unstructured":"Reinefeld, A., Sch\u00fctt, T.: Out-of-core parallel frontier search with MapReduce. In: Mewhort, D.J.K., Cann, N.M., Slater, G.W., Naughton, T.J. (eds.) HPCS 2009. LNCS, vol. 5976, pp. 323\u2013336. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-12659-8_24"},{"key":"6_CR81","doi-asserted-by":"crossref","unstructured":"Reinefeld, A., Sch\u00fctt, T., D\u00f6bbelin, R.: Very large pattern databases for heuristic search. In: Hariri, S., Keahey, K. (eds.), HPDC, pp. 803\u2013809 (2010)","DOI":"10.1145\/1851476.1851592"},{"key":"6_CR82","unstructured":"Richter, S., Helmert, M., Westphal, M.: Landmarks revisited. In: AAAI, pp. 975\u2013982 (2008)"},{"issue":"2","key":"6_CR83","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1137\/120867366","volume":"27","author":"T Rokicki","year":"2013","unstructured":"Rokicki, T., Kociemba, H., Davidson, M., Dethridge, J.: The diameter of the Rubik\u2019s cube group is twenty. SIAM J. Discrete Math. 27(2), 1082\u20131105 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"6_CR84","unstructured":"Rosin, C.D.: Nested rollout policy adaptation for Monte-Carlo tree search. In: IJCAI, pp. 649\u2013654 (2011)"},{"key":"6_CR85","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms for Memory Hierarchies","year":"2003","unstructured":"Meyer, U., Sanders, P., Sibeyn, J. (eds.): Algorithms for Memory Hierarchies. LNCS, vol. 2625. Springer, Heidelberg (2003)"},{"key":"6_CR86","unstructured":"Schaeffer, J., Bj\u00f6rnsson, Y., Burch, N., Kishimoto, A., M\u00fcller, M.: Solving checkers. In: IJCAI, pp. 292\u2013297 (2005)"},{"issue":"5844","key":"6_CR87","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1126\/science.1144079","volume":"317","author":"J Schaeffer","year":"2007","unstructured":"Schaeffer, J., Burch, N., Bjrnsson, Y., Kishimoto, A., M\u00fcller, M., Lake, R., Lu, S.S.P.: Checkers is solved. Science 317(5844), 1518\u20131522 (2007)","journal-title":"Science"},{"key":"6_CR88","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1613\/jair.1534","volume":"23","author":"S Schroedl","year":"2005","unstructured":"Schroedl, S.: An improved search algorithm for optimal multiple sequence alignment. J. Artif. Intell. Res. 23, 587\u2013623 (2005)","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"6_CR89","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1002\/cpe.1833","volume":"25","author":"T Sch\u00fctt","year":"2013","unstructured":"Sch\u00fctt, T., Reinefeld, A., Maier, R.: MR-search: massively parallel heuristic search. Concurr. Comput.: Pract. Exp. 25(1), 40\u201354 (2013)","journal-title":"Concurr. Comput.: Pract. Exp."},{"key":"6_CR90","unstructured":"Sturtevant, N.R.: External memory PDBs: initial results. In: SARA (2013)"},{"key":"6_CR91","unstructured":"Sturtevant, N.R., Rutherford, M.J.: Minimizing writes in parallel external memory search. In: IJCAI (2013)"},{"key":"6_CR92","unstructured":"Wijs, A.: What to do Next? Analysing and optimising system behaviour in time. PhD thesis, Vrije Universiteit Amsterdam (1999)"},{"key":"6_CR93","unstructured":"Zhou, R., Hansen, E.: Breadth-first heuristic search. In: ICAPS, pp. 92\u2013100 (2004)"},{"key":"6_CR94","unstructured":"Zhou, R., Hansen, E.: Structured duplicate detection in external-memory graph search. In: AAAI, pp. 683\u2013689 (2004)"},{"key":"6_CR95","unstructured":"Zhou, R., Hansen, E.: External-memory pattern databases using structured duplicate detection. In: AAAI (2005)"},{"key":"6_CR96","unstructured":"Zhou, R., Hansen, E.A.: Multiple sequence alignment using A*. In: AAAI (2002). Student abstract"},{"key":"6_CR97","unstructured":"Zhou, R., Hansen, E.A.: Edge partitioning in external-memory graph search. In: IJCAI, pp. 2410\u20132417 (2007)"},{"key":"6_CR98","unstructured":"Zhou, R., Hansen, E.A.: Parallel structured duplicate detection. In: AAAI, pp. 1217\u20131222 (2007)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-49487-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T14:01:14Z","timestamp":1718892074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-49487-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319494869","9783319494876"],"references-count":98,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-49487-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"11 November 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}