<div class="csl-bib-body">
<div class="csl-entry">Deligkas, A., Eiben, E., Ganian, R., Kanj, I., Leko, D., & Ramanujan, M. S. (2025). Routing Few Robots in a Crowded Network. In P. Morin & E. Oh (Eds.), <i>19th International Symposium on Algorithms and Data Structures (WADS 2025)</i>. Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.WADS.2025.20</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/222175
-
dc.description.abstract
In Graph Coordinated Motion Planning, we are given a graph G some of whose vertices are occupied by robots, and we are asked to route k marked robots to their destinations while avoiding collisions and without exceeding a given budget ℓ on the number of robot moves. We continue the recent investigation of the problem [ICALP 2024], focusing on the parameter k that captures the task of routing a small number of robots in a possibly crowded graph. We prove that the problem is W[1]-hard parameterized by ℓ even for k = 1, but fixed-parameter tractable parameterized by k plus the treedepth of G. We complement the latter algorithm with an NP-hardness reduction which shows that both parameters are necessary to achieve tractability.
en
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics
-
dc.subject
graph coordinated motion planning
en
dc.subject
parameterized complexity
en
dc.subject
treedepth
en
dc.title
Routing Few Robots in a Crowded Network
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
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
TU Wien, Austria
-
dc.contributor.affiliation
University of Warwick, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.editoraffiliation
Carleton University, Canada
-
dc.contributor.editoraffiliation
Pohang University of Science and Technology, Korea (the Republic of)
-
dc.relation.isbn
978-3-95977-398-0
-
dc.relation.issn
1868-8969
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
19th International Symposium on Algorithms and Data Structures (WADS 2025)
-
tuw.container.volume
349
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl
-
tuw.relation.publisherplace
Leibniz
-
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.WADS.2025.20
-
dc.description.numberOfPages
15
-
tuw.author.orcid
0000-0002-6513-6748
-
tuw.author.orcid
0000-0003-2628-3435
-
tuw.author.orcid
0000-0002-7762-8045
-
tuw.author.orcid
0000-0003-1698-8829
-
tuw.author.orcid
0009-0008-2969-1120
-
tuw.author.orcid
0000-0002-2116-6048
-
tuw.event.name
WADS 2025
-
tuw.event.startdate
11-08-2025
-
tuw.event.enddate
15-08-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Toronto
-
tuw.event.country
CA
-
tuw.event.presenter
Deligkas, Argyrios
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.grantfulltext
none
-
item.openairetype
conference paper
-
item.languageiso639-1
en
-
crisitem.author.dept
University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
DePaul University, United States of America (the)
-
crisitem.author.dept
TU Wien, Austria
-
crisitem.author.dept
University of Warwick, United Kingdom of Great Britain and Northern Ireland (the)
