Abstract
Given a tree, a set of pebbles initially stationed at some nodes of the tree and a set of target nodes, the Unlabeled Pebble Motion on Trees problem (UPMT) asks to find a plan to move the pebbles one-at-a-time from the starting nodes to the target nodes along the edges of the tree while minimizing the number of moves. This paper proposes the first optimal algorithm for UPMT that is asymptotically as fast as possible, as it runs in a time linear in the size of the input (the tree) and the size of the output (the optimal plan).
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 17th International Symposium on Combinatorial Search |
| Editors | Ariel Felner, Jiaoyang Li |
| Place of Publication | Washington DC USA |
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Pages | 218-222 |
| Number of pages | 5 |
| ISBN (Electronic) | 139781577358916, 101577358910 |
| DOIs | |
| Publication status | Published - 2024 |
| Event | International Symposium on Combinatorial Search 2024 - Pomeroy Kananaskis Mountain Lodge, Kananaskis, Canada Duration: 6 Jun 2024 → 8 Jun 2024 Conference number: 17th https://ojs.aaai.org/index.php/SOCS/issue/view/607 (Proceedings) https://socs24.search-conference.org/ (Conference website) |
Publication series
| Name | Proceedings of the International Symposium on Combinatorial Search |
|---|---|
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Number | 1 |
| Volume | 17 |
| ISSN (Print) | 2832-9171 |
| ISSN (Electronic) | 2832-9163 |
Conference
| Conference | International Symposium on Combinatorial Search 2024 |
|---|---|
| Abbreviated title | SoCS 2024 |
| Country/Territory | Canada |
| City | Kananaskis |
| Period | 6/06/24 → 8/06/24 |
| Internet address |
|