7 papers
Precoloring extension with demands on paths
Arun Kumar Das, Michal Opler, Tomáš Valla
Let be a graph with a set of precolored vertices, and let us be given an integer distance parameter and a set of integer demands . The Distance Precoloring E…
Pathfinding in Self-Deleting Graphs
Michal DvoÅák, DuÅ¡an Knop, Michal Opler +3
In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we st…
Density of Traceable Graphs
Michal DvoÅák, DuÅ¡an Knop, Michal Opler +3
We establish tight lower and upper bounds on the number of edges in traceable graphs in several classes of dense graphs. A graph is traceable if it has a Hamiltonian path. We show…
When Agents Break Down in Multiagent Path Finding
Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos +1
In Multiagent Path Finding (MAPF), the goal is to compute efficient, collision-free paths for multiple agents navigating a network from their sources to targets, minimizing the sch…
Solving Multiagent Path Finding on Highly Centralized Networks
Foivos Fioravantes, DuÅ¡an Knop, Jan Matyáš KÅiÅ¡Å¥an +3
The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destin…
Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
Foivos Fioravantes, DuÅ¡an Knop, Jan Matyáš KÅiÅ¡Å¥an +2
Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean…