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 <>
Submitted on : Friday, May 19, 2006 - 8:36:47 PM
Last modification on : Wednesday, October 14, 2020 - 4:23:12 AM
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