EUVIMEDEUVIMED entdecken
Crossref

On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs

Bernhard Nebel

Proceedings of the International Conference on Automated Planning and Scheduling · 01.06.2020 · 30 · 212-216

DOI: 10.1609/icaps.v30i1.6663 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 01.06.2020. Verfasst von Bernhard Nebel. Die Arbeit wurde bisher 14-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs can be decided in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven.

Zitieren

APA

Nebel, B. (2020). On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs. Proceedings of the International Conference on Automated Planning and Scheduling, 30, 212-216. https://doi.org/10.1609/icaps.v30i1.6663

Vancouver

Nebel B. On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs. Proceedings of the International Conference on Automated Planning and Scheduling. 2020;30:212-216. doi:10.1609/icaps.v30i1.6663

BibTeX
@article{Nebel2020,
  author = {Nebel, Bernhard},
  title = {On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2020},
  volume = {30},
  pages = {212--216},
  doi = {10.1609/icaps.v30i1.6663}
}
Kostenlos starten →