Bibliography¶
The references are those of the README of the repository, with the same numbers, so that a citation [N] means the same work in both; each is given with its doi where it has one.
[1] A. Fukunaga, A. Botea, Y. Jinnai and A. Kishimoto, A Survey of Parallel A*, arXiv:1708.05296, 2017.
[2] A. Kishimoto, A. Fukunaga and A. Botea, Evaluation of a simple, scalable, parallel best-first search strategy, Artificial Intelligence 195, 222-248, 2013.
[3] E. Burns, S. Lemons, W. Ruml and R. Zhou, Best-first heuristic search for multicore machines, Journal of Artificial Intelligence Research 39, 689-743, 2010.
[4] E. Burns, M. Hatem, M. J. Leighton and W. Ruml, Implementing fast heuristic search code, Proceedings of the Symposium on Combinatorial Search (SoCS) 3, 25-32, 2012.
[5] Y. Jinnai and A. Fukunaga, On hash-based work distribution methods for parallel best-first search, Journal of Artificial Intelligence Research 60, 491-548, 2017.
[6] M. Phillips, M. Likhachev and S. Koenig, PA*SE: Parallel A* for slow expansions, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 24, 208-216, 2014.
[7] R. E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence 27, 97-109, 1985.
[8] N. J. Nilsson, Principles of Artificial Intelligence, Tioga, 1980; reprinted by Springer, 1982.
[9] P. E. Hart, N. J. Nilsson and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4(2), 100-107, 1968.
[10] S. Edelkamp and S. Schroedl, Heuristic Search: Theory and Applications, Morgan Kaufmann, 2012.
[11] F. Mattern, Algorithms for distributed termination detection, Distributed Computing 2(3), 161-175, 1987.
[12] M. Aldinucci, M. Danelutto, P. Kilpatrick and M. Torquati, FastFlow: high-level and efficient streaming on multicore, in Programming Multi-core and Many-core Computing Systems, Wiley, 261-280, 2017.
[13] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 3rd edition, Prentice Hall, 2010.
[14] M. Held and R. M. Karp, A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics 10(1), 196-210, 1962.
[15] N. R. Sturtevant, Benchmarks for grid-based pathfinding, IEEE Transactions on Computational Intelligence and AI in Games 4(2), 144-148, 2012.
[16] B. Gendron and T. G. Crainic, Parallel branch-and-bound algorithms: survey and synthesis, Operations Research 42(6), 1042-1066, 1994.
[17] D. S. Nau, V. Kumar and L. Kanal, General branch and bound, and its relation to A* and AO*, Artificial Intelligence 23(1), 29-58, 1984.
[18] Y. Shinano, S. Heinz, S. Vigerske and M. Winkler, FiberSCIP: a shared memory parallelization of SCIP, INFORMS Journal on Computing 30(1), 11-30, 2018.
[19] M. Fischetti, M. Monaci and D. Salvagnin, Self-splitting of workload in parallel computation, Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2014), Lecture Notes in Computer Science 8451, 394-404, 2014.
[20] R. D. Blumofe and C. E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM 46(5), 720-748, 1999.
[21] J. C. Culberson and J. Schaeffer, Pattern databases, Computational Intelligence 14(3), 318-334, 1998.
[22] R. E. Korf and A. Felner, Disjoint pattern database heuristics, Artificial Intelligence 134(1-2), 9-22, 2002.
[23] A. Felner, R. E. Korf and S. Hanan, Additive pattern database heuristics, Journal of Artificial Intelligence Research 22, 279-318, 2004.
[24] A. Felner, R. E. Korf, R. Meshulam and R. C. Holte, Compressed pattern databases, Journal of Artificial Intelligence Research 30, 213-247, 2007.
[25] T. Breyer and R. E. Korf, 1.6-bit pattern databases, Proceedings of the AAAI Conference on Artificial Intelligence 24, 39-44, 2010.
[26] R. E. Korf, Minimizing disk I/O in two-bit breadth-first search, Proceedings of the AAAI Conference on Artificial Intelligence 23, 317-324, 2008.
[27] R. Clausecker and A. Reinefeld, Zero-aware pattern databases with 1-bit compression for sliding tile puzzles, Proceedings of the Symposium on Combinatorial Search (SoCS) 10, 35-43, 2019.
[28] F. Yang, J. Culberson, R. Holte, U. Zahavi and A. Felner, A general theory of additive state space abstractions, Journal of Artificial Intelligence Research 32, 631-662, 2008.
[29] U. Zahavi, A. Felner, R. C. Holte and J. Schaeffer, Duality in permutation state spaces and the dual search algorithm, Artificial Intelligence 172(4-5), 514-540, 2008.
[30] R. C. Holte, A. Felner, J. Newton, R. Meshulam and D. Furcy, Maximizing over multiple pattern databases speeds up heuristic search, Artificial Intelligence 170(16-17), 1123-1136, 2006.
[31] A. Felner, U. Zahavi, R. Holte, J. Schaeffer, N. Sturtevant and Z. Zhang, Inconsistent heuristics in theory and practice, Artificial Intelligence 175(9-10), 1570-1603, 2011.
[32] T. Nagahashi and D. Takahashi, Construction of large zero-aware pattern databases for sliding puzzles on distributed memory machines, Computational Science and Its Applications (ICCSA 2025), Lecture Notes in Computer Science, 272-284, 2025.
[33] M. Samadi, M. Siabani, A. Felner and R. Holte, Compressing pattern databases with learning, Proceedings of the European Conference on Artificial Intelligence (ECAI 2008), Frontiers in Artificial Intelligence and Applications 178, 2008.
[34] W. Myrvold and F. Ruskey, Ranking and unranking permutations in linear time, Information Processing Letters 79(6), 281-284, 2001.
[35] E. W. Dijkstra and C. S. Scholten, Termination detection for diffusing computations, Information Processing Letters 11(1), 1-4, 1980.
[36] D. Hendler and N. Shavit, Non-blocking steal-half work queues, Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 280-289, 2002.
[37] H. Rihani, P. Sanders and R. Dementiev, MultiQueues: simple relaxed concurrent priority queues, Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 80-82, 2015.
[38] A. Postnikova, N. Koval, G. Nadiradze and D. Alistarh, Multi-queues can be state-of-the-art priority schedulers, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 353-367, 2022.
[39] S. Edelkamp, S. Jabbar and S. Schrödl, External A*, KI 2004: Advances in Artificial Intelligence, Lecture Notes in Computer Science 3238, 226-240, 2004.
[40] R. E. Korf, Linear-time disk-based implicit graph search, Journal of the ACM 55(6), 26:1-26:40, 2008.
[41] T. Ikeda and H. Imai, Enhanced A* algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases, Theoretical Computer Science 210(2), 341-374, 1999.
[42] T. Yoshizumi, T. Miura and T. Ishida, A* with partial expansion for large branching factor problems, Proceedings of the AAAI Conference on Artificial Intelligence 17, 923-929, 2000.
[43] Y. Kobayashi, A. Kishimoto and O. Watanabe, Evaluations of Hash Distributed A* in optimal sequence alignment, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 22, 584-589, 2011.
[44] M. O. Dayhoff, R. M. Schwartz and B. C. Orcutt, A model of evolutionary change in proteins, Atlas of Protein Sequence and Structure 5, supplement 3, 345-352, 1978.
[45] J. D. Thompson, P. Koehl, R. Ripp and O. Poch, BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark, Proteins 61(1), 127-136, 2005.
[46] I. Pohl, Heuristic search viewed as path finding in a graph, Artificial Intelligence 1(3-4), 193-204, 1970.
[47] E. A. Hansen and R. Zhou, Anytime heuristic search, Journal of Artificial Intelligence Research 28, 267-297, 2007.
[48] M. Likhachev, G. Gordon and S. Thrun, ARA*: Anytime A* with provable bounds on sub-optimality, Advances in Neural Information Processing Systems (NIPS) 16, 767-774, 2003.
[49] J. T. Thayer and W. Ruml, Faster than weighted A*: an optimistic approach to bounded suboptimal search, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 18, 355-362, 2008.
[50] J. Chen, N. R. Sturtevant, W. Doyle and W. Ruml, Revisiting suboptimal search, Proceedings of the Symposium on Combinatorial Search (SoCS) 10, 18-25, 2019.
[51] J. Pearl and J. H. Kim, Studies in semi-admissible heuristics, IEEE Transactions on Pattern Analysis and Machine Intelligence 4(4), 392-399, 1982.
[52] J. T. Thayer and W. Ruml, Bounded suboptimal search: a direct approach using inadmissible estimates, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 22, 674-679, 2011.
[53] D. Gilon, A. Felner and R. Stern, Dynamic potential search: a new bounded suboptimal search algorithm, Proceedings of the Symposium on Combinatorial Search (SoCS) 7, 36-44, 2016.
[54] S. Koenig, M. Likhachev and D. Furcy, Lifelong Planning A*, Artificial Intelligence 155(1-2), 93-146, 2004.
[55] A. Reinefeld and V. Schnecke, AIDA*: asynchronous parallel IDA*, Proceedings of the Biennial Conference of the Canadian Society for Computational Studies of Intelligence (AI 94), 295-302, 1994.
[56] Z. Bu and R. E. Korf, A*+IDA*: a simple hybrid search algorithm, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 28, 1206-1212, 2019.
[57] L. Siag, S. S. Shperberg, A. Felner and N. R. Sturtevant, On parallel external-memory bidirectional search, Proceedings of the European Conference on Artificial Intelligence (ECAI 2024), Frontiers in Artificial Intelligence and Applications 392, 4190-4197, 2024.
[58] V. N. Rao and V. Kumar, Parallel depth first search. Part I. Implementation, International Journal of Parallel Programming 16(6), 479-499, 1987.
[59] R. E. Korf, Finding optimal solutions to Rubik's Cube using pattern databases, Proceedings of the AAAI Conference on Artificial Intelligence 14, 700-705, 1997.
[60] M. Helmert, Landmark heuristics for the pancake problem, Proceedings of the Symposium on Combinatorial Search (SoCS) 1, 109-110, 2010.
[61] R. C. Holte, A. Felner, G. Sharon and N. R. Sturtevant, Bidirectional search that is guaranteed to meet in the middle, Proceedings of the AAAI Conference on Artificial Intelligence 30, 2016.
[62] B. Bonet, Efficient algorithms to rank and unrank permutations in lexicographic order, AAAI Workshop on Search in Artificial Intelligence and Robotics, Technical Report WS-08-10, 18-23, 2008.
[63] H. Dweighter, Problem E2569, in Elementary Problems: E2564-E2569, The American Mathematical Monthly 82(10), 1009, 1975.
[64] C. Demetrescu, A. V. Goldberg and D. S. Johnson (editors), The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 74, AMS, 2009.
[65] R. B. Dial, Algorithm 360: shortest-path forest with topological ordering, Communications of the ACM 12(11), 632-633, 1969.
[66] R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics 17(2), 416-429, 1969.
[67] B. Archibald, P. Maier, R. Stewart and P. Trinder, Replicable parallel branch and bound search, Journal of Parallel and Distributed Computing 113, 92-114, 2018.
[68] B. Archibald, P. Maier, R. Stewart and P. Trinder, YewPar: skeletons for exact combinatorial search, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) 25, 292-307, 2020.
[69] Y. Shinano, T. Achterberg, T. Berthold, S. Heinz, T. Koch and M. Winkler, Solving open MIP instances with ParaSCIP on supercomputers using up to 80,000 cores, Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS) 30, 770-779, 2016.
[70] Y. Xu, T. K. Ralphs, L. Ladányi and M. J. Saltzman, ALPS: a framework for implementing parallel tree search algorithms, The Next Wave in Computing, Optimization, and Decision Technologies, 319-334, Springer, 2005.
[71] M. Mezmaz, R. Leroy, N. Melab and D. Tuyttens, A multi-core parallel branch-and-bound algorithm using factorial number system, Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS) 28, 1203-1212, 2014.
[72] J. Gmys, R. Leroy, M. Mezmaz, N. Melab and D. Tuyttens, Work stealing with private integer-vector-matrix data structure for multi-core branch-and-bound algorithms, Concurrency and Computation: Practice and Experience 28(18), 4463-4484, 2016.
[73] S. Olivier, J. Huan, J. Liu, J. Prins, J. Dinan, P. Sadayappan and C.-W. Tseng, UTS: an unbalanced tree search benchmark, Languages and Compilers for Parallel Computing (LCPC) 19, Lecture Notes in Computer Science 4382, 235-250, 2007.
[74] E. Tomita and T. Kameda, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, Journal of Global Optimization 37(1), 95-111, 2007.
[75] P. San Segundo, D. Rodríguez-Losada and A. Jiménez, An exact bit-parallel algorithm for the maximum clique problem, Computers & Operations Research 38(2), 571-581, 2011.
[76] C. McCreesh, P. Prosser and J. Trimble, A partitioning algorithm for maximum common subgraph problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 26, 712-719, 2017.
[77] P. C. Gilmore, Optimal and suboptimal algorithms for the quadratic assignment problem, Journal of the Society for Industrial and Applied Mathematics 10(2), 305-313, 1962.
[78] R. E. Burkard, S. E. Karisch and F. Rendl, QAPLIB - a quadratic assignment problem library, Journal of Global Optimization 10(4), 391-403, 1997.
[79] B. J. Lageweg, J. K. Lenstra and A. H. G. Rinnooy Kan, A general bounding scheme for the permutation flow-shop problem, Operations Research 26(1), 53-67, 1978.
[80] E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research 64(2), 278-285, 1993.
[81] R. C. Holte, A. Felner, G. Sharon, N. R. Sturtevant and J. Chen, MM: A bidirectional search algorithm that is guaranteed to meet in the middle, Artificial Intelligence 252, 232-266, 2017.
[82] G. Sharon, R. C. Holte, A. Felner and N. R. Sturtevant, Extended abstract: an improved priority function for bidirectional heuristic search, Proceedings of the Symposium on Combinatorial Search (SoCS) 7, 139-140, 2016.
[83] E. Shaham, A. Felner, J. Chen and N. R. Sturtevant, The minimal set of states that must be expanded in a front-to-end bidirectional search, Proceedings of the Symposium on Combinatorial Search (SoCS) 8, 82-90, 2017.
[84] J. Eckerle, J. Chen, N. R. Sturtevant, S. Zilles and R. C. Holte, Sufficient conditions for node expansion in bidirectional heuristic search, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 27, 79-87, 2017.
[85] J. Chen, R. C. Holte, S. Zilles and N. R. Sturtevant, Front-to-end bidirectional heuristic search with near-optimal node expansions, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 489-495, 2017.
[86] S. S. Shperberg, A. Felner, N. R. Sturtevant, S. E. Shimony and A. Hayoun, Enriching non-parametric bidirectional search algorithms, Proceedings of the AAAI Conference on Artificial Intelligence 33, 2379-2386, 2019.
[87] M. Barley, P. Riddle, C. Linares López, S. Dobson and I. Pohl, GBFHS: A generalized breadth-first heuristic search algorithm, Proceedings of the Symposium on Combinatorial Search (SoCS) 9, 28-36, 2018.
[88] S. K. Sadhukhan, Bidirectional heuristic search based on error estimate, CSI Journal of Computing 2(1-2), S1, 2013.
[89] V. Alcázar, P. J. Riddle and M. Barley, A unifying view on individual bounds and heuristic inaccuracies in bidirectional search, Proceedings of the AAAI Conference on Artificial Intelligence 34, 2327-2334, 2020.
[90] J. B. H. Kwa, BS*: An admissible bidirectional staged heuristic search algorithm, Artificial Intelligence 38(1), 95-109, 1989.
[91] I. Pohl, Bi-directional search, Machine Intelligence 6, 127-140, 1971.
[92] W. Pijls and H. Post, A new bidirectional search algorithm with shortened postprocessing, European Journal of Operational Research 198(2), 363-369, 2009.
[93] L. H. O. Rios and L. Chaimowicz, PNBA*: A parallel bidirectional heuristic search algorithm, Proceedings of the Encontro Nacional de Inteligência Artificial (ENIA) 8, 2011.
[94] N. R. Sturtevant and J. Chen, External memory bidirectional search, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 676-682, 2016.
[95] S. Lin and A. Fukunaga, Revisiting immediate duplicate detection in external memory search, Proceedings of the AAAI Conference on Artificial Intelligence 32, 2018.
[96] J. E. Doran and D. Michie, Experiments with the Graph Traverser program, Proceedings of the Royal Society A 294, 235-259, 1966.
[97] S. Richter and M. Helmert, Preferred operators and deferred evaluation in satisficing planning, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 19, 273-280, 2009.
[98] G. Röger and M. Helmert, The more, the merrier: combining heuristic estimators for satisficing planning, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 20, 246-249, 2010.
[99] F. Xie, M. Müller, R. Holte and T. Imai, Type-based exploration with multiple search queues for satisficing planning, Proceedings of the AAAI Conference on Artificial Intelligence 28, 2014.
[100] R. A. Valenzano, N. R. Sturtevant, J. Schaeffer and F. Xie, A comparison of knowledge-based GBFS enhancements and knowledge-free exploration, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 24, 375-379, 2014.
[101] J. Hoffmann and B. Nebel, The FF planning system: fast plan generation through heuristic search, Journal of Artificial Intelligence Research 14, 253-302, 2001.
[102] S. Richter and M. Westphal, The LAMA planner: guiding cost-based anytime planning with landmarks, Journal of Artificial Intelligence Research 39, 127-177, 2010.
[103] S. Richter, J. T. Thayer and W. Ruml, The joy of forgetting: faster anytime search via restarting, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 20, 137-144, 2010.
[104] N. Lipovetzky and H. Geffner, Width and serialization of classical planning problems, Proceedings of the European Conference on Artificial Intelligence (ECAI 2012), Frontiers in Artificial Intelligence and Applications 242, 540-545, 2012.
[105] N. Lipovetzky and H. Geffner, Best-first width search: exploration and exploitation in classical planning, Proceedings of the AAAI Conference on Artificial Intelligence 31, 2017.
[106] V. Vidal, L. Bordeaux and Y. Hamadi, Adaptive K-parallel best-first search: a simple but efficient algorithm for multi-core domain-independent planning, Proceedings of the Symposium on Combinatorial Search (SoCS) 1, 100-107, 2010.
[107] R. Kuroiwa and A. Fukunaga, On the pathological search behavior of distributed greedy best-first search, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 29, 255-263, 2019.
[108] R. Kuroiwa and A. Fukunaga, Analyzing and avoiding pathological behavior in parallel best-first search, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 30, 175-183, 2020.
[109] T. Shimoda and A. Fukunaga, Improved exploration of the bench transition system in parallel greedy best first search, Proceedings of the Symposium on Combinatorial Search (SoCS) 16, 74-82, 2023.
[110] T. Shimoda and A. Fukunaga, Parallel greedy best-first search with a bound on expansions relative to sequential search, Proceedings of the AAAI Conference on Artificial Intelligence 39, 26668-26677, 2025.
[111] T. Shimoda and A. Fukunaga, Decoupling generation and evaluation for parallel greedy best-first search, arXiv:2408.05682, 2024.
[112] M. Heusner, T. Keller and M. Helmert, Understanding the search behaviour of greedy best-first search, Proceedings of the Symposium on Combinatorial Search (SoCS) 8, 47-55, 2017.
[113] A. Felner, M. Goldenberg, G. Sharon, R. Stern, T. Beja, N. R. Sturtevant, J. Schaeffer and R. C. Holte, Partial-expansion A* with selective node generation, Proceedings of the AAAI Conference on Artificial Intelligence 26, 471-477, 2012.
[114] M. Goldenberg, A. Felner, R. Stern, G. Sharon, N. Sturtevant, R. C. Holte and J. Schaeffer, Enhanced partial expansion A*, Journal of Artificial Intelligence Research 50, 141-187, 2014.
[115] Y. Björnsson, M. Enzenberger, R. C. Holte and J. Schaeffer, Fringe search: beating A* at pathfinding on game maps, Proceedings of the IEEE Symposium on Computational Intelligence and Games (CIG 2005), 125-132, 2005.
[116] R. E. Korf, Linear-space best-first search, Artificial Intelligence 62(1), 41-78, 1993.
[117] R. Zhou and E. A. Hansen, Beam-stack search: integrating backtracking with beam search, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 15, 90-98, 2005.
[118] R. E. Korf, Real-time heuristic search, Artificial Intelligence 42(2-3), 189-211, 1990.
[119] S. Koenig and X. Sun, Comparing real-time and incremental heuristic search for real-time situated agents, Autonomous Agents and Multi-Agent Systems 18(3), 313-341, 2009.
[120] A. Botea, M. Müller and J. Schaeffer, Near optimal hierarchical path-finding, Journal of Game Development 1(1), 7-28, 2004.
[121] S. Mukherjee, S. Aine and M. Likhachev, ePA*SE: Edge-based parallel A* for slow evaluations, Proceedings of the International Symposium on Combinatorial Search (SoCS) 15, 136-144, 2022.
[122] S. Mukherjee and M. Likhachev, GePA*SE: Generalized edge-based parallel A* for slow evaluations, Proceedings of the International Symposium on Combinatorial Search (SoCS) 16, 153-157, 2023.
[123] H. Yang, S. Mukherjee and M. Likhachev, A-ePA*SE: Anytime edge-based parallel A* for slow evaluations, Proceedings of the International Symposium on Combinatorial Search (SoCS) 16, 163-167, 2023.
[124] S. Mukherjee, S. Aine and M. Likhachev, MPLP: Massively parallelized lazy planning, IEEE Robotics and Automation Letters 7(3), 6067-6074, 2022.
[125] C. M. Dellin and S. S. Srinivasa, A unifying formalism for shortest path problems with expensive edge evaluations via lazy best-first search over paths with edge selectors, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 26, 459-467, 2016.
[126] F. Agostinelli, S. McAleer, A. Shmakov and P. Baldi, Solving the Rubik's cube with deep reinforcement learning and search, Nature Machine Intelligence 1, 356-363, 2019.
[127] M. Evett, J. Hendler, A. Mahanti and D. Nau, PRA*: massively parallel heuristic search, Journal of Parallel and Distributed Computing 25(2), 133-143, 1995.
[128] R. Zhou and E. A. Hansen, Parallel structured duplicate detection, Proceedings of the AAAI Conference on Artificial Intelligence 22, 1217-1223, 2007.
[129] R. Zhou and E. A. Hansen, Breadth-first heuristic search, Artificial Intelligence 170(4-5), 385-408, 2006.
[130] A. Felner, S. Kraus and R. E. Korf, KBFS: K-best-first search, Annals of Mathematics and Artificial Intelligence 39(1-2), 19-39, 2003.
[131] J. W. Romein, A. Plaat, H. E. Bal and J. Schaeffer, Transposition table driven work scheduling in distributed search, Proceedings of the AAAI Conference on Artificial Intelligence 16, 725-731, 1999.
[132] U. K. Sarkar, P. P. Chakrabarti, S. Ghose and S. C. De Sarkar, Reducing reexpansions in iterative-deepening search by controlling cutoff bounds, Artificial Intelligence 50(2), 207-221, 1991.
[133] C. Bäckström and B. Nebel, Complexity results for SAS+ planning, Computational Intelligence 11(4), 625-655, 1995.
[134] M. Helmert, The Fast Downward planning system, Journal of Artificial Intelligence Research 26, 191-246, 2006.
[135] B. Bonet and H. Geffner, Planning as heuristic search, Artificial Intelligence 129(1-2), 5-33, 2001.
[136] M. Helmert and C. Domshlak, Landmarks, critical paths and abstractions: what's the difference anyway?, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 19, 162-169, 2009.
[137] S. Edelkamp, Planning with pattern databases, Proceedings of the European Conference on Planning (ECP), 13-24, 2001.
[138] Y. Jinnai and A. Fukunaga, Automated creation of efficient work distribution functions for parallel best-first search, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 26, 184-192, 2016.
[139] R. Zhou and E. A. Hansen, Domain-independent structured duplicate detection, Proceedings of the AAAI Conference on Artificial Intelligence 21, 1082-1087, 2006.
[140] M. Helmert, P. Haslum, J. Hoffmann and R. Nissim, Merge-and-shrink abstraction: a method for generating lower bounds in factored state spaces, Journal of the ACM 61(3), 16:1-16:63, 2014.
[141] Y. Jinnai and A. Fukunaga, Abstract Zobrist hashing: an efficient work distribution method for parallel best-first search, Proceedings of the AAAI Conference on Artificial Intelligence 30, 717-723, 2016.
[142] C. M. Fiduccia and R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th Design Automation Conference, 175-181, 1982.
[143] S. Koenig and M. Likhachev, D* Lite, Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) 18, 476-483, 2002; and Fast replanning for navigation in unknown terrain, IEEE Transactions on Robotics 21(3), 354-363, 2005.
[144] G. Ramalingam and T. Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms 21(2), 267-305, 1996.
[145] U. Meyer and P. Sanders, Δ-stepping: a parallelizable shortest path algorithm, Journal of Algorithms 49(1), 114-152, 2003.
[146] A. H. Land and A. G. Doig, An automatic method of solving discrete programming problems, Econometrica 28(3), 497-520, 1960.
[147] G. B. Dantzig, Discrete-variable extremum problems, Operations Research 5(2), 266-288, 1957.
[148] D. Pisinger, Where are the hard knapsack problems?, Computers & Operations Research 32(9), 2271-2284, 2005.
[149] T.-H. Lai and S. Sahni, Anomalies in parallel branch-and-bound algorithms, Communications of the ACM 27(6), 594-602, 1984.
[150] W. W. Johnson and W. E. Story, Notes on the "15" Puzzle, American Journal of Mathematics 2(4), 397-404, 1879.
[151] D. Lemire, Fast random integer generation in an interval, ACM Transactions on Modeling and Computer Simulation 29(1), 1-12, 2019.
[152] A. L. Zobrist, A new hashing method with application for game playing, Technical Report 88, Computer Sciences Department, University of Wisconsin, 1970; reprinted in ICGA Journal 13(2), 69-73, 1990.
[153] V. Kumar, K. Ramesh and V. N. Rao, Parallel best-first search of state-space graphs: a summary of results, Proceedings of the AAAI Conference on Artificial Intelligence 7, 122-127, 1988.
[154] R. M. Karp and Y. Zhang, Randomized parallel algorithms for backtrack search and branch-and-bound computation, Journal of the ACM 40(3), 765-789, 1993.
[155] K. B. Irani and Y. Shih, Parallel A* and AO* algorithms: an optimality criterion and performance evaluation, Proceedings of the International Conference on Parallel Processing (ICPP), 274-277, 1986.
[156] R. E. Korf and P. Schultze, Large-scale parallel breadth-first search, Proceedings of the AAAI Conference on Artificial Intelligence 20, 1380-1385, 2005.
[157] D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998.
[158] D. B. Johnson, Priority queues with update and finding minimum spanning trees, Information Processing Letters 4(3), 53-57, 1975.
[159] D. R. Hanson, Fast allocation and deallocation of memory based on object lifetimes, Software: Practice and Experience 20(1), 5-12, 1990.
[160] R. K. Ahuja, K. Mehlhorn, J. B. Orlin and R. E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM 37(2), 213-223, 1990.
[161] A. Reinefeld and T. A. Marsland, Enhanced iterative-deepening search, IEEE Transactions on Pattern Analysis and Machine Intelligence 16(7), 701-710, 1994.
[162] T. Miura and T. Ishida, Stochastic node caching for memory-bounded search, Systems and Computers in Japan 30(2), 57-65, 1999.
[163] R. E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers C-35(8), 677-691, 1986.
[164] Y. Jinnai, Introduction to heuristic search (in Japanese), lecture notes, 175 pages, version of 9 December 2023, available from https://jinnaiyuu.github.io/.
[165] N. R. Sturtevant, HOG2: Hierarchical Open Graph, software, Moving AI Lab, University of Denver.
[166] E. L. Lawler, The quadratic assignment problem, Management Science 9(4), 586-599, 1963.
[167] A. Felner, U. Zahavi, J. Schaeffer and R. C. Holte, Dual lookups in pattern databases, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 19, 103-108, 2005.
[168] R. Nissim, J. Hoffmann and M. Helmert, Computing perfect heuristics in polynomial time: on bisimulation and merge-and-shrink abstraction in optimal planning, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 22, 1983-1990, 2011.
[169] A. R. Karlin, M. S. Manasse, L. Rudolph and D. D. Sleator, Competitive snoopy caching, Algorithmica 3(1-4), 79-119, 1988.
[170] N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd edition, SIAM, 2002.
[171] B. T. Lowerre, The HARPY speech recognition system, PhD thesis, Carnegie Mellon University, 1976.
[172] H. Kociemba, kociemba.org/cube.htm, web pages on the two-phase algorithm for Rubik's cube and its cubie model, consulted in November 2026.
[173] E. Keyder and H. Geffner, Heuristics for planning with action costs revisited, Proceedings of the European Conference on Artificial Intelligence (ECAI), Frontiers in Artificial Intelligence and Applications 178, 588-592, 2008.
[174] D. S. Johnson and M. A. Trick (editors), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26, American Mathematical Society, 1996.
[175] C. Bron and J. Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM 16(9), 575-577, 1973.
[176] T. C. Koopmans and M. Beckmann, Assignment problems and the location of economic activities, Econometrica 25(1), 53-76, 1957.
[177] H. W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly 2(1-2), 83-97, 1955.
[178] S. M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1(1), 61-68, 1954.
[179] National Institute of Standards and Technology, Secure Hash Standard (SHS), Federal Information Processing Standards Publication 180-4, 2015.
[180] L. Mandow and J. L. Pérez de la Cruz, Multiobjective A* search with consistent heuristics, Journal of the ACM 57(5), 1-25, 2010.
[181] C. Hernández, W. Yeoh, J. A. Baier, H. Zhang, L. Suazo, S. Koenig and O. Salzman, Simple and efficient bi-objective search algorithms via fast dominance checks, Artificial Intelligence 314, 103807, 2023.
[182] Z. Ren, R. Zhan, S. Rathinam, M. Likhachev and H. Choset, Enhanced multi-objective A* using balanced binary search trees, Proceedings of the International Symposium on Combinatorial Search (SoCS) 15, 162-170, 2022.
[183] C. Hernández, W. Yeoh, J. A. Baier, A. Felner, O. Salzman, H. Zhang, S.-H. Chan and S. Koenig, Multi-objective search via lazy and efficient dominance checks, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) 32, 7223-7230, 2023.
[184] S. Ahmadi, N. R. Sturtevant, A. Raith, D. Harabor and M. Jalili, Parallelizing multi-objective A* search, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 35, 131-139, 2025.
[185] F.-J. Pulido, L. Mandow and J. L. Pérez de la Cruz, Dimensionality reduction in multiobjective shortest path search, Computers & Operations Research 64, 60-70, 2015.
[186] P. Sanders and L. Mandow, Parallel label-setting multi-objective shortest path search, Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS) 27, 215-224, 2013.
[187] X. Xu, N. Zhang, L. Qian, X. Liu, J. Wu and H. Tang, Asynchronous parallel search for exact multi-objective shortest paths with versioned frontier snapshots and indexed dominance pruning, arXiv:2609.11944, 2026.
[188] P. Maristany de las Casas, L. Kraus, A. Sedeño-Noda and R. Borndörfer, Targeted multiobjective Dijkstra algorithm, Networks 82(3), 277-298, 2023.
[189] P. M. Fenwick, A new data structure for cumulative frequency tables, Software: Practice and Experience 24(3), 327-336, 1994.
[190] J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill and L. J. Hwang, Symbolic model checking: 10^20 states and beyond, Information and Computation 98(2), 142-170, 1992.
[191] S. Edelkamp and F. Reffel, OBDDs in heuristic search, KI-98: Advances in Artificial Intelligence, Lecture Notes in Computer Science 1504, 81-92, 1998.
[192] R. M. Jensen, M. M. Veloso and R. E. Bryant, State-set branching: Leveraging BDDs for heuristic search, Artificial Intelligence 172(2-3), 103-139, 2008.
[193] Á. Torralba, V. Alcázar, P. Kissmann and S. Edelkamp, Efficient symbolic search for cost-optimal planning, Artificial Intelligence 242, 52-79, 2017.
[194] T. van Dijk and J. van de Pol, Sylvan: multi-core framework for decision diagrams, International Journal on Software Tools for Technology Transfer 19(6), 675-696, 2017.
[195] D. Speck, R. Mattmüller and B. Nebel, Symbolic top-k planning, Proceedings of the AAAI Conference on Artificial Intelligence 34, 9967-9974, 2020.
[196] S. Edelkamp and P. Kissmann, Optimal symbolic planning with action costs and preferences, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1690-1695, 2009.
[197] F. Somenzi, CUDD: CU Decision Diagram package, release 3.0.0, University of Colorado at Boulder, 2015.
[198] Á. Torralba, V. Alcázar, D. Borrajo, P. Kissmann and S. Edelkamp, SymBA*: A symbolic bidirectional A* planner, The 2014 International Planning Competition: Description of Planners, 105-109, 2014.
[199] A. Felner and N. Ofek, Combining perimeter search and pattern database abstractions, Abstraction, Reformulation, and Approximation (SARA), Lecture Notes in Computer Science 4612, 155-168, 2007.
[200] J. Seipp and M. Helmert, Counterexample-guided Cartesian abstraction refinement, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 23, 347-351, 2013.
[201] J. Seipp and M. Helmert, Counterexample-guided Cartesian abstraction refinement for classical planning, Journal of Artificial Intelligence Research 62, 535-577, 2018.
[202] J. Seipp and M. Helmert, Diverse and additive Cartesian abstraction heuristics, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) 24, 289-297, 2014.