The robot cleans up |
| |
Authors: | M. E. Messinger R. J. Nowakowski |
| |
Affiliation: | 1. Department of Math. & Stats., Dalhousie University, Halifax, NS, B3H 3J5, Canada
|
| |
Abstract: | Imagine a large building with many corridors. A robot cleans these corridors in a greedy fashion, the next corridor cleaned is always the dirtiest to which it is incident. We determine bounds on the minimum s(G) and maximum S(G) number of time steps (over all edge weightings) before every edge of a graph G has been cleaned. We show that Eulerian graphs have a self-stabilizing property that holds for any initial edge weighting: after the initial cleaning of all edges, all subsequent cleanings require s(G) time steps. Finally, we show the only self-stabilizing trees are a subset of the superstars. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|