<div class="csl-bib-body">
<div class="csl-entry">Eiben, E., Ganian, R., Kanj, I., & Ramanujan, M. S. (2025). A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots. In <i>41st International Symposium on Computational Geometry (SoCG 2025)</i>. 41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan. Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.SoCG.2025.44</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/220016
-
dc.description.abstract
We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the Coordinated Sliding-Motion Planning (CSMP) problem. In this variant, we are given an undirected graph G, k robots R1,...,Rk positioned on distinct vertices of G, p ≤ k distinct destination vertices for robots R1,...,Rp, and ℓ ∈ N. The problem is to decide if there is a serial schedule of at most ℓ moves (i.e., of makespan ℓ) such that at the end of the schedule each robot with a destination reaches it, where a robot's move is a free path (unoccupied by any robots) from its current position to an unoccupied vertex. The problem is known to be NP-hard even on full grids. It has been studied in several contexts, including coin movement and reconfiguration problems, with respect to feasibility, complexity, and approximation. Geometric variants of the problem, in which congruent geometric-shape robots (e.g., unit disk/squares) slide or translate in the Euclidean plane, have also been studied extensively. We investigate the parameterized complexity of CSMP with respect to two parameters: the number k of robots and the makespan ℓ. As our first result, we present a fixed-parameter algorithm for CSMP parameterized by k. For our second result, we present a fixed-parameter algorithm parameterized by ℓ for the special case of CSMP in which only a single robot has a destination and the graph is planar. A crucial new ingredient for both of our results is that the solution admits a succinct representation as a small labeled topological minor of the input graph.
en
dc.language.iso
en
-
dc.subject
coordinated motion planning on graphs
en
dc.subject
parameterized complexity
en
dc.subject
planar graphs
en
dc.subject
topological minor testing
en
dc.title
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Royal Holloway University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
DePaul University, United States of America (the)
-
dc.contributor.affiliation
University of Warwick Science Park, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.relation.isbn
978-3-95977-370-6
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
41st International Symposium on Computational Geometry (SoCG 2025)
-
tuw.container.volume
332
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl
-
tuw.relation.publisherplace
Leibniz-Zentrum für Informatik
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publication.orgunit
E056-13 - Fachbereich LogiCS
-
tuw.publisher.doi
10.4230/LIPIcs.SoCG.2025.44
-
dc.description.numberOfPages
15
-
tuw.author.orcid
0000-0003-2628-3435
-
tuw.author.orcid
0000-0002-7762-8045
-
tuw.author.orcid
0000-0003-1698-8829
-
tuw.author.orcid
0000-0002-2116-6048
-
tuw.event.name
41st International Symposium on Computational Geometry (SoCG 2025)
en
tuw.event.startdate
23-06-2025
-
tuw.event.enddate
27-06-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Kanazawa
-
tuw.event.country
JP
-
tuw.event.presenter
Eiben, Eduard
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.fulltext
no Fulltext
-
crisitem.author.dept
TU Wien
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
DePaul University, United States of America (the)
-
crisitem.author.dept
University of Warwick Science Park, United Kingdom of Great Britain and Northern Ireland (the)