BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.4.5//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:0-280@lisn.upsaclay.fr
DTSTART;TZID=Europe/Paris:20250620T140000
DTEND;TZID=Europe/Paris:20250620T140000
DTSTAMP:20250613T074655Z
URL:https://www.lisn.upsaclay.fr/evenements/scheduling-and-graph-explorati
 on-with-deadlines/
SUMMARY:Scheduling and graph-exploration with deadlines
DESCRIPTION:Consider a graph with weights on its edges and nodes. A node we
 ight represents a (time) deadline for this node and an edge weight represe
 nts the time a robot needs to traverse this edge. A robot needs to visit e
 ach node of the graph within its deadline. Can we decide in polynomial tim
 e whether such a `successful’ exploration is possible?\nWe survey this a
 rea of research first focusing on a clique topology where each node must b
 e visited not just once but periodically and the maximum allowed time-peri
 od between any two consecutive visits of the same node should not exceed i
 ts deadline. This case has been introduced as a scheduling problem known a
 s ‘Pinwheel’ and quite a few questions remain open for more than 30 ye
 ars. We compare the computational complexity of this case with the complex
 ity of the case where each node must be visited at least once within its d
 eadline (and not periodically). We also present some results in other sele
 cted topologies.\nThe above exploration-scheduling problems find applicati
 ons in areas like mobile monitoring and facility service and maintenance.\
 nBiography\nEuripides Markou is a Professor at the Department of Computer
  Science &amp\; Engineering of the University of Ioannina\, Greece\, and a
 n affiliated researcher of Archimedes\, Athena Research Center. He receiv
 ed his B.Sc. degree (in Physics) from the University of Ioannina and his P
 h.D. degree (in Theoretical Computer Science) from the National Technical 
 University of Athens. He has been a postdoctoral researcher at the Univers
 ite du Quebec en Outaouais\, Gatineau\, Canada\, at the National and Kapod
 istrian University of Athens\, at the Laboratoire Bordelais de Recherche e
 n 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 Inf
 ormatics (2008 - 2024)\, University of Thessaly. His research interests in
 clude the design of algorithms and the study of computational complexity f
 or problems particularly in the areas of distributed computing\, algorithm
 ic game theory\, computational geometry and computational biology.\nPlace\
 nLISN\, 1 rue Raimond Castaing\, 91190 Gif-sur-Yvette - Room 445.
CATEGORIES:AAC
LOCATION:LISN Site Plaine\, 1 rue Raimond Castaing   91190 Gif-sur-Yvette\,
  France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=1 rue Raimond Castaing   91
 190 Gif-sur-Yvette\, France;X-APPLE-RADIUS=100;X-TITLE=LISN Site Plaine:ge
 o:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20250330T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR