5 papers
Parameterized Critical Node Cut Revisited
Dušan Knop, Nikolaos Melissinos, Manolis Vasilakis
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph and integers , Critical Node Cut (CNC) asks whether we can delete at mos…
Parameterized Complexity of Scheduling Problems in Robotic Process Automation
Michal DvoÅák, AntonÃn Novák, PÅemysl Šůcha +2
This paper studies the growing domain of Robotic Process Automation (RPA) problems. Motivated by scheduling problems arising in RPA, we study the parameterized complexity of the si…
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…
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…