Tech Reports


On-line Dominating Sets in Web Graphs

Colin Cooper, Ralf Klasing and Michele Zito


In this paper we study the size of generalised dominating sets in two recently proposed models of the web graph. On the one hand, we show that web graphs have fairly large dominating sets (i.e. ~linear in the size of the graph). On the other hand, we present on-line strategies to construct reasonable dominating sets. The proof of the algorithmic bounds is based on an adaptation of the differential equation method to the on-line setting, and may be of independent interest. Available from the authors upon request.