Seminár z teoretickej informatiky - Stefan Dobrev (29.4.2016)

v piatok 29.4.2016 o 11:00 hod. v miestnosti M/213

25. 04. 2016 15.18 hod.
Od: Rastislav Kráľovič

Prednášajúci: Stefan Dobrev

Názov: Live Exploration of Dynamic Rings

Termín: 29.4.2016,11:00 hod., M/213

Abstrakt:
Almost all the vast literature on graph exploration assumes that the graph is static: its topology does not change during the exploration, except for occasional faults. To date, very little is known on exploration of dynamic graphs, where the topology is continously changing. The few studies have been limited to the centralized (or post-mortem) case, assuming complete a priori knowledge of the changes and the times of their occurrence, and have only considered fully synchronous systems.
In this paper, we start the study of the decentralized (or live) exploration of dynamic graphs, i.e. when the agents operate in the graph unaware of the location and timing of the changes. We consider dynamic rings under the standard 1-interval-connected restriction, and investigate the feasibility of their exploration, in both the fully synchronous and semi-synchronous cases. When exploration is possible we examine at what cost, focusing on the minimum number of agents capable of exploring the ring. We establish several results highlighting the impact that anonymity and structural knowledge have on the feasibility and complexity of the problem.
podľa: G.A. Di Luna (University of Ottawa), S. Dobrev (Slovak Academy of Sciences), P. Flocchini (University of Ottawa) N. Santoro (Carleton University), Live Exploration of Dynamic Rings, To appear at ICDCS 2016
Tešíme sa na Vašu účasť.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php