Lower Bounds and Algorithms for Dominating Sets in Web Graphs
Cooper, Colin ; Klasing, Ralf ; Zito, Michele
Internet Math., Tome 2 (2005) no. 2, p. 275-300 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
In this paper we study the size of generalised dominating sets in two graph processes that are widely used to model aspects of the World Wide Web. On the one hand, we show that graphs generated this way have fairly large dominating sets (i.e., linear in the size of the graph). On the other hand, we present efficient strategies to construct small dominating sets. ¶ The algorithmic results represent an application of a particular analysis technique which can be used to characterise the asymptotic behaviour of a number of dynamic processes related to the web.
Publié le : 2005-05-14
Classification:  
@article{1150474884,
     author = {Cooper, Colin and Klasing, Ralf and Zito, Michele},
     title = {Lower Bounds and Algorithms for Dominating Sets in Web Graphs},
     journal = {Internet Math.},
     volume = {2},
     number = {2},
     year = {2005},
     pages = { 275-300},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1150474884}
}

Cooper, Colin; Klasing, Ralf; Zito, Michele. Lower Bounds and Algorithms for Dominating Sets in Web Graphs. Internet Math., Tome 2 (2005) no. 2, pp.  275-300. http://gdmltest.u-ga.fr/item/1150474884/