Scheduling and graph-exploration with deadlines

Consider a graph with weights on its edges and nodes. A node weight represents a (time) deadline for this node and an edge weight represents the time a robot needs to traverse this edge. A robot needs to visit each node of the graph within its deadline. Can we decide in polynomial time whether such a `successful’ exploration is possible?

We survey this area of research first focusing on a clique topology where each node must be visited not just once but periodically and the maximum allowed time-period between any two consecutive visits of the same node should not exceed its deadline. This case has been introduced as a scheduling problem known as ‘Pinwheel’ and quite a few questions remain open for more than 30 years. We compare the computational complexity of this case with the complexity of the case where each node must be visited at least once within its deadline (and not periodically). We also present some results in other selected topologies.

The above exploration-scheduling problems find applications in areas like mobile monitoring and facility service and maintenance.

Biography

Euripides Markou is a Professor at the Department of Computer Science & Engineering of the University of Ioannina, Greece, and an affiliated researcher of Archimedes, Athena Research Center. He received his B.Sc. degree (in Physics) from the University of Ioannina and his Ph.D. degree (in Theoretical Computer Science) from the National Technical University of Athens. He has been a postdoctoral researcher at the Universite du Quebec en Outaouais, Gatineau, Canada, at the National and Kapodistrian University of Athens, at the Laboratoire Bordelais de Recherche en Informatique, Bordeaux, France and at McMaster University, Hamilton, Canada. Before joining the University of Ioannina in 2024, he had held a faculty position at the Department of Computer Science and Biomedical Informatics (2008 – 2024), University of Thessaly. His research interests include the design of algorithms and the study of computational complexity for problems particularly in the areas of distributed computing, algorithmic game theory, computational geometry and computational biology.

Place

LISN, 1 rue Raimond Castaing, 91190 Gif-sur-Yvette – Room 445.