A Self-stabilizing Algorithm for Graph Searching in Trees

Autor:	Rodica Mihai, Morten Mjelde
Rok vydání:	2009
Předmět:	SPQR tree Theoretical computer science Graph bandwidth Computer science Chordal graph Tree network Graph (abstract data type) Tree decomposition Algorithm Feedback arc set Connectivity Graph Moral graph
Zdroj:	Lecture Notes in Computer Science ISBN: 9783642051173 SSS
DOI:	10.1007/978-3-642-05118-0_39
Popis:	Graph searching games have been extensively studied in the past years. The graph searching problem involves a team of searchers who are attempting to capture a fugitive moving along the edges of the graph. In this paper we consider the graph searching problem in a network environment, namely a tree network. Searchers are software programs and the fugitive is a virus that spreads rapidly. Every node of the network which the virus may have reached, becomes contaminated. The purpose of the game is to clean the network. In real world distributed systems faults can occur and thus it is desirable for an algorithm to be able to facilitate the cleaning of a network in an optimal way, and also to reconfigure on the fly. In this paper we give the first self-stabilizing algorithm for solving the graph searching problem in trees. Our algorithm stabilizes after O (n 3) time steps under the distributed adversarial daemon. Our algorithm solves the node searching variant of the graph searching problem, but can with small modifications also solve edge and mixed searching.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::ea3ff1bb0962449fb45a0da473fbcfdc https://doi.org/10.1007/978-3-642-05118-0_39 Zobrazit plný text záznamu