The Maximum Rooted Connected Expansion problem

Graduate Thesis uoadl:2885008 127 Read counter

Department of Informatics and Telecommunications
Deposit date:
Supervisors info:
Βασίλειος Ζησιμόπουλος, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
The Maximum Rooted Connected Expansion problem
Translated title:
The Maximum Rooted Connected Expansion problem
Graph theory has many applications in modern world. Our study on it crossed paths
with an intresting problem called Prefetching. Prefetching constitutes a valuable tool
toward the goal of effiecient Web Surfing. An important issue in prefetching is the
tradeoff between the amount of network’s resources wasted by the prefetching and the
gain of time. For instance, in the Web, browsers may download documents in advance
while a Web surfer is surfing on the Web. Since the Web surfer follows the hyperlinks in
an unpredictable way, the choice of the Web pages to be prefetched must be computed
online. The question is then to determine the minimum amount of resources used by
prefetching that ensures that all documents accessed by the Web surfer have
previously been loaded in the cache. In this regard, prefetching can be modeled as a
two-player combinatorial game.
Motivated by the above Sigalas et al. considered the following maximization problem to
which they refer to as the Maximum Rooted Connected Expansion (MRCE) problem
which is NP-hard. Given a graph G and a root node u 0 , we wish to find a subset of
vertices S such that S is connected, S contains u 0 and the ratio N [S ]/|S|
is maximized, where N [S ] denotes the closed neighbourhood of S , that is
N [S ] contains all nodes in S and all nodes with at least one neighbour in S .
We further discuss their approach on the way of solving this problem through an
approximation algorithm. We studied other significant problems on graph theory like
Connected Dominating Set, Maximum Leaf Spanning Tree and their special case
problems so as to understand the structure and connection between all those and
MRCE. As result of that study we mapped those problems according to their connection
and interaction between them. Our contribution is a greedy algorithm for the MRCE
which we believe through our experimental analysis could eventually lead to a small
approximation, result.
Main subject category:
Technology - Computer science
Prefetching, connected dominating set, expansion, ratio, maximum leaf
Number of index pages:
Contains images:
Number of references:
Number of pages:
ThesisNT.pdf (492 KB) Open in new window