{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:28:33Z","timestamp":1742934513167,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319575858"},{"type":"electronic","value":"9783319575865"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-57586-5_21","type":"book-chapter","created":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T15:23:34Z","timestamp":1492097014000},"page":"247-259","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds"],"prefix":"10.1007","author":[{"given":"Klaus-Tycho","family":"Foerster","sequence":"first","affiliation":[]},{"given":"Linus","family":"Groner","sequence":"additional","affiliation":[]},{"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Koenig","sequence":"additional","affiliation":[]},{"given":"Sascha","family":"Schmid","sequence":"additional","affiliation":[]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,14]]},"reference":[{"issue":"1","key":"21_CR1","doi-asserted-by":"publisher","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(1), 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"2","key":"21_CR2","doi-asserted-by":"publisher","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 the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"issue":"4","key":"21_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/961261.961263","volume":"37","author":"R Scott","year":"2003","unstructured":"Scott, R.: Sparking life: notes on the performance capture sessions for the lord of the rings: the two towers. SIGGRAPH Comput. Graph. 37(4), 17\u201321 (2003)","journal-title":"SIGGRAPH Comput. Graph."},{"key":"21_CR4","unstructured":"Silver, D.: Cooperative pathfinding. In: Artificial Intelligence and Interactive Digital Entertainment Conference (2005)"},{"issue":"4","key":"21_CR5","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.autcon.2007.06.005","volume":"17","author":"N Pelechano","year":"2008","unstructured":"Pelechano, N., Malkawi, A.: Evacuation simulation models: challenges in modeling high rise building evacuation with cellular automata approaches. Autom. Constr. 17(4), 377\u2013385 (2008)","journal-title":"Autom. Constr."},{"issue":"3","key":"21_CR6","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0921-8890(97)00033-X","volume":"23","author":"P Svestka","year":"1998","unstructured":"Svestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23(3), 125\u2013152 (1998)","journal-title":"Robot. Auton. Syst."},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Domke, J., Hoefler, T., Matsuoka, S.: Routing on the dependency graph: a new approach to deadlock-free high-performance routing. In: Symposium on High-Performance Parallel and Distributed Computing (2016)","DOI":"10.1145\/2907294.2907313"},{"key":"21_CR8","series-title":"Springer Tracts in Advanced Robotics","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/978-3-319-16595-0_42","volume-title":"Algorithmic Foundations of Robotics XI","author":"J Yu","year":"2015","unstructured":"Yu, J., Rus, D.: Pebble motion on graphs with rotations: efficient feasibility tests and planning algorithms. In: Akin, H.L., Amato, N.M., Isler, V., Stappen, A.F. (eds.) Algorithmic Foundations of Robotics XI. STAR, vol. 107, pp. 729\u2013746. Springer, Cham (2015). doi:10.1007\/978-3-319-16595-0_42"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Driscoll, J.R., Furst, M.L.: On the diameter of permutation groups. In: Symposium on Theory of Computing (1983)","DOI":"10.1145\/800061.808744"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Kornhauser, D., Miller, G., Spirakis, P.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: Symposium on Foundations of Computer Science (1984)","DOI":"10.1109\/SFCS.1984.715921"},{"issue":"4","key":"21_CR11","doi-asserted-by":"publisher","first-page":"397","DOI":"10.2307\/2369492","volume":"2","author":"WW Johnson","year":"1879","unstructured":"Johnson, W.W.: Notes on the \u201c15\u201d puzzle. Am. J. Math. 2(4), 397\u2013404 (1879)","journal-title":"Am. J. Math."},{"issue":"1","key":"21_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"RM Wilson","year":"1974","unstructured":"Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Comb. Theory, Ser. B 16(1), 86\u201396 (1974)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"21_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D Ratner","year":"1990","unstructured":"Ratner, D., Warmuth, M.: The $$n^2-1$$ puzzle and related relocation problems. J. Symb. Comput. 10(2), 111\u2013137 (1990)","journal-title":"J. Symb. Comput."},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-22670-0_1","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay Between Randomness and Computation","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O.: Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay Between Randomness and Computation. LNCS, vol. 6650, pp. 1\u20135. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-22670-0_1"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Kornhauser, D.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. Master\u2019s thesis MIT\/LCS\/TR-320, Massachusetts Institute of Technology (1984)","DOI":"10.1109\/SFCS.1984.715921"},{"key":"21_CR16","unstructured":"R\u00f6ger, G., Helmert, M.: Non-optimal multi-agent pathfinding is solved (since 1984). In: Symposium on Combinatorial Search (2012)"},{"key":"21_CR17","volume-title":"Basic Algebra","author":"N Jacobson","year":"1974","unstructured":"Jacobson, N.: Basic Algebra. Freeman, San Francisco (1974)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-57586-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T14:49:22Z","timestamp":1710341362000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-57586-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319575858","9783319575865"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-57586-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"14 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/ciac2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}