{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T14:37:58Z","timestamp":1777559878419,"version":"3.51.4"},"reference-count":39,"publisher":"SAGE Publications","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIC"],"published-print":{"date-parts":[[2016,5,30]]},"DOI":"10.3233\/aic-160704","type":"journal-article","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T08:08:19Z","timestamp":1464682099000},"page":"513-536","source":"Crossref","is-referenced-by-count":2,"title":["Optimally solving permutation sorting problems with efficient partial expansion bidirectional heuristic search"],"prefix":"10.1177","volume":"29","author":[{"given":"Marco","family":"Lippi","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica \u2013 Scienza e Ingegneria, Universit\u00e0 degli Studi di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy. E-mail:\u00a0marco.lippi3@unibo.it"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Ernandes","sequence":"additional","affiliation":[{"name":"Quest-IT s.r.l., Strada Massetana Romana, 44, 53100 Siena, Italy. E-mail:\u00a0ernandes@quest-it.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Felner","sequence":"additional","affiliation":[{"name":"Department of Information System Engineering, Ben Gurion University, Be\u2019er-Sheva, Israel. E-mail:\u00a0felner@bgu.ac.il"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"issue":"2","key":"10.3233\/AIC-160704_ref1","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1137\/S0097539793250627","article-title":"Genome rearrangements and sorting by reversals","volume":"25","author":"Bafna","year":"1996","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.3233\/AIC-160704_ref2","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S089548019528280X","article-title":"Sorting by transpositions","volume":"11","author":"Bafna","year":"1998","journal-title":"SIAM J. Discrete Math."},{"key":"10.3233\/AIC-160704_ref3","doi-asserted-by":"crossref","unstructured":"J.K.\u00a0Barker and R.E.\u00a0Korf, Limitations of front-to-end bidirectional heuristic search, in: Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.","DOI":"10.1609\/aaai.v29i1.9374"},{"key":"10.3233\/AIC-160704_ref4","doi-asserted-by":"crossref","unstructured":"A.\u00a0Bergeron, J.\u00a0Mixtacki and J.\u00a0Stoye, On sorting by translocations, in: Research in Computational Molecular Biology, Lecture Notes in Computer Science, Vol.\u00a03500, Springer, Berlin, Heidelberg, 2005, pp.\u00a0615\u2013629.","DOI":"10.1007\/11415770_47"},{"key":"10.3233\/AIC-160704_ref5","doi-asserted-by":"crossref","unstructured":"L.\u00a0Bulteau, G.\u00a0Fertin and I.\u00a0Rusu, Pancake flipping is hard, in: Mathematical Foundations of Computer Science (MFCS) 2012, Lecture Notes in Computer Science, Vol.\u00a07464, Springer, 2012, pp.\u00a0247\u2013258.","DOI":"10.1007\/978-3-642-32589-2_24"},{"issue":"3","key":"10.3233\/AIC-160704_ref6","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/110851390","article-title":"Sorting by transpositions is difficult","volume":"26","author":"Bulteau","year":"2012","journal-title":"SIAM J. Discrete Math."},{"key":"10.3233\/AIC-160704_ref7","doi-asserted-by":"crossref","unstructured":"A.\u00a0Caprara, Sorting by reversals is difficult, in: First Annual International Conference on Computational Molecular Biology (RECOMB), ACM, 1997, pp.\u00a075\u201383.","DOI":"10.1145\/267521.267531"},{"issue":"4","key":"10.3233\/AIC-160704_ref8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0020-0190(96)00155-X","article-title":"Sorting permutations by block-interchanges","volume":"60","author":"Christie","year":"1996","journal-title":"Information Processing Letters"},{"issue":"8\u201310","key":"10.3233\/AIC-160704_ref9","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1016\/j.tcs.2010.11.028","article-title":"On average and highest number of flips in pancake sorting","volume":"412","author":"Cibulka","year":"2011","journal-title":"Theoretical Computer Science"},{"key":"10.3233\/AIC-160704_ref10","unstructured":"\u00c1.T.A.\u00a0de\u00a0Reyna and C.\u00a0Linares L\u00f3pez, Size-independent additive pattern databases for the pancake problem, in: Fourth Annual Symposium on Combinatorial Search, SoCS 2011, AAAI Press, 2011."},{"issue":"4","key":"10.3233\/AIC-160704_ref11","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1109\/TCBB.2006.44","article-title":"A 1.375-approximation algorithm for sorting by transpositions","volume":"3","author":"Elias","year":"2006","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"10.3233\/AIC-160704_ref12","unstructured":"A.\u00a0Felner, M.\u00a0Goldenberg, G.\u00a0Sharon, R.\u00a0Stern, T.\u00a0Beja, N.R.\u00a0Sturtevant, J.\u00a0Schaeffer and R.\u00a0Holte, Partial-expansion A\u2217 with selective node generation, in: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, 2012."},{"key":"10.3233\/AIC-160704_ref13","unstructured":"A.\u00a0Felner, C.\u00a0Moldenhauer, N.R.\u00a0Sturtevant and J.\u00a0Schaeffer, Single-frontier bidirectional search, in: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, 11\u201315 July 2010, AAAI Press, 2010."},{"issue":"9,10","key":"10.3233\/AIC-160704_ref14","doi-asserted-by":"crossref","first-page":"1570","DOI":"10.1016\/j.artint.2011.02.001","article-title":"Inconsistent heuristics in theory and practice","volume":"175","author":"Felner","year":"2011","journal-title":"Artificial Intelligence"},{"key":"10.3233\/AIC-160704_ref15","unstructured":"J.\u00a0Feng and D.\u00a0Zhu, Faster algorithms for sorting by transpositions and sorting by block interchanges, ACM Trans. Algorithms 3(3) (2007), Article No.\u00a025."},{"issue":"1","key":"10.3233\/AIC-160704_ref16","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","article-title":"Bounds for sorting by prefix reversal","volume":"27","author":"Gates","year":"1979","journal-title":"Discrete Mathematics"},{"key":"10.3233\/AIC-160704_ref17","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1613\/jair.4171","article-title":"Enhanced partial expansion A\u2217","volume":"50","author":"Goldenberg","year":"2014","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"issue":"2","key":"10.3233\/AIC-160704_ref18","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0304-3975(98)00092-9","article-title":"A 2-approximation algorithm for genome rearrangements by reversals and transpositions","volume":"210","author":"Gu","year":"1999","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"10.3233\/AIC-160704_ref19","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0166-218X(96)00061-3","article-title":"Polynomial-time algorithm for computing translocation distance between genomes","volume":"71","author":"Hannenhalli","year":"1996","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"10.3233\/AIC-160704_ref20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","article-title":"Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals","volume":"46","author":"Hannenhalli","year":"1999","journal-title":"J. ACM"},{"issue":"2","key":"10.3233\/AIC-160704_ref21","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"issue":"13","key":"10.3233\/AIC-160704_ref22","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0166-218X(98)00072-9","article-title":"Sorting by bounded block-moves","volume":"88","author":"Heath","year":"1998","journal-title":"Discrete Applied Mathematics"},{"key":"10.3233\/AIC-160704_ref23","doi-asserted-by":"crossref","unstructured":"M.\u00a0Helmert, Landmark heuristics for the pancake problem, in: SoCS 2010, AAAI Press, 2010.","DOI":"10.1609\/socs.v1i1.18176"},{"key":"10.3233\/AIC-160704_ref24","doi-asserted-by":"crossref","unstructured":"R.C.\u00a0Holte, A.\u00a0Felner, G.\u00a0Sharon and N.R.\u00a0Sturtevant, Bidirectional search that is guaranteed to meet in the middle, in: Thirtieth AAAI Conference on Artificial Intelligence, 2016.","DOI":"10.1016\/j.artint.2017.05.004"},{"key":"10.3233\/AIC-160704_ref25","unstructured":"R.C.\u00a0Holte and I.T.\u00a0Hern\u00e1dv\u00f6lgyi, A space-time tradeoff for memory-based heuristics, in: Sixteenth National Conference on Artificial Intelligence and Eleventh Conference on Innovative Applications of Artificial Intelligence, AAAI Press\/The MIT Press, 1999, pp.\u00a0704\u2013709."},{"key":"10.3233\/AIC-160704_ref26","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1613\/jair.460","article-title":"Bidirectional heuristic search reconsidered","volume":"7","author":"Kaindl","year":"1997","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1,2","key":"10.3233\/AIC-160704_ref27","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01188586","article-title":"Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement","volume":"13","author":"Kececioglu","year":"1995","journal-title":"Algorithmica"},{"key":"10.3233\/AIC-160704_ref28","unstructured":"M.\u00a0Keshtkaran, R.\u00a0Taghizadeh and K.\u00a0Ziarati, A novel technique for compressing pattern databases in the pancake sorting problems, in: SOCS, AAAI Press, 2011."},{"key":"10.3233\/AIC-160704_ref29","unstructured":"R.E.\u00a0Korf, Iterative-deepening-A\u2217: An optimal admissible tree search, in: 9th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1985, pp.\u00a01034\u20131036."},{"issue":"80","key":"10.3233\/AIC-160704_ref30","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/j.tcs.2010.11.004","article-title":"Polynomial-time sortable stacks of burnt pancakes","volume":"412","author":"Labarre","year":"2011","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"10.3233\/AIC-160704_ref31","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1109\/TSMCC.2005.855522","article-title":"Algorithmic approaches for genome rearrangement: A review","volume":"36","author":"Li","year":"2006","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews"},{"key":"10.3233\/AIC-160704_ref32","unstructured":"M.\u00a0Lippi, M.\u00a0Ernandes and A.\u00a0Felner, Efficient single frontier bidirectional search, in: Fifth Annual Symposium on Combinatorial Search (SoCS) 2012, AAAI Press, 2012."},{"key":"10.3233\/AIC-160704_ref33","doi-asserted-by":"crossref","unstructured":"K.\u00a0Qiu, H.\u00a0Meijer and S.\u00a0Akl, Parallel routing and sorting on the pancake network, in: Advances in Computing and Information ICCI\u201991, Lecture Notes in Computer Science, Vol.\u00a0497, Springer, Berlin, Heidelberg, 1991, pp.\u00a0360\u2013371.","DOI":"10.1007\/3-540-54029-6_184"},{"key":"10.3233\/AIC-160704_ref34","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","article-title":"Conflict-based search for optimal multi-agent pathfinding","volume":"219","author":"Sharon","year":"2015","journal-title":"Artificial Intelligence"},{"key":"10.3233\/AIC-160704_ref35","first-page":"319","article-title":"Sorting circular permutations by reversal","volume":"2003","author":"Solomon","year":"2003","journal-title":"WADS"},{"issue":"3","key":"10.3233\/AIC-160704_ref36","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1093\/bioinformatics\/18.3.492","article-title":"Grimm: Genome rearrangements web server","volume":"18","author":"Tesler","year":"2002","journal-title":"Bioinformatics"},{"issue":"16","key":"10.3233\/AIC-160704_ref38","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"Efficient sorting of genomic permutations by translocation, inversion and block interchange","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"},{"key":"10.3233\/AIC-160704_ref39","unstructured":"T.\u00a0Yoshizumi, T.\u00a0Miura and T.\u00a0Ishida, A\u2217 with partial expansion for large branching factor problems, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, AAAI Press, 2000, pp.\u00a0923\u2013929."},{"issue":"13","key":"10.3233\/AIC-160704_ref40","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.tcs.2005.09.078","article-title":"On the complexity of unsigned translocation distance","volume":"352","author":"Zhu","year":"2006","journal-title":"Theoretical Computer Science"}],"container-title":["AI Communications"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/AIC-160704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T18:27:27Z","timestamp":1777400847000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/AIC-160704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,30]]},"references-count":39,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.3233\/aic-160704","relation":{},"ISSN":["1875-8452","0921-7126"],"issn-type":[{"value":"1875-8452","type":"electronic"},{"value":"0921-7126","type":"print"}],"subject":[],"published":{"date-parts":[[2016,5,30]]}}}