4 papers
PSPACE-completeness of the Hunters and Rabbit game
Walid Ben-Ameur, Alessandro Maddaloni
In the Hunters and Rabbit game, hunters shoot at a set of vertices at each round, while an invisible rabbit must move along an edge. We prove that deciding whether a given number o…
Common Optimal Supports and Bottleneck Hierarchies in Truncated Cones
Walid Ben-Ameur, Alessandro Maddaloni
{Let \(K\subseteq\mathbb R_+^E\) be a closed convex cone and \(P=K\cap[0,1]^E\). For a linear objective with positive optimum, we study the intersection of the coordinate supports…
Hunting a rabbit: complexity, approximability and some characterizations
Walid Ben-Ameur, Harmender Gahlawat, Alessandro Maddaloni
In the Hunters and Rabbit game, hunters attempt to shoot an invisible rabbit on a given graph . In each round, the hunters select vertices to shoot at, while the rabbit…
Complexity results for a cops and robber game on directed graphs
Walid Ben-Ameur, Alessandro Maddaloni
We investigate a cops and robber game on directed graphs, where the robber moves along the arcs of the graph, while the cops can select any position at each time step. Our main foc…