HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Lower Bounds and Algorithms for Dominating Sets in Web Graphs

Colin Cooper 1 Ralf Klasing 1, 2 Michele Zito 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper we study the size of dominating sets, and their generalizations, in two graph processes which are widely used to model aspects of the world-wide web. In these processes each new vertex connects to the existing graph by a constant number, $m$, of edges. The terminal vertices of these edges are chosen uniformly at random or by preferential attachment depending on the process. We show that almost all such graph processes have minimal dominating sets linear in the size of the graph and give bounds for this size as a function of $m$. We obtain the upper bounds from simple on-line algorithms for dominating sets. The lower bounds are obtained by proving that the lexicographically first set of a given size is the most likely to dominate.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:36:47 PM
Last modification on : Monday, December 20, 2021 - 4:50:11 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:18:37 PM


  • HAL Id : inria-00070478, version 1


Colin Cooper, Ralf Klasing, Michele Zito. Lower Bounds and Algorithms for Dominating Sets in Web Graphs. [Research Report] RR-5529, INRIA. 2006, pp.26. ⟨inria-00070478⟩



Record views


Files downloads