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

# Lower Bounds and Algorithms for Dominating Sets in Web Graphs

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.
Keywords :
Document type :
Reports
Domain :

Cited literature [1 references]

https://hal.inria.fr/inria-00070478
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

### Identifiers

• HAL Id : inria-00070478, version 1

### Citation

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