Tech Reports
ULCS-03-019
On-line Dominating Sets in Web Graphs
Abstract
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.
For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.
Maintained by webmaster@csc.liv.ac.uk