Graduate Thesis uoadl:2885008 52 Read counter

Department of Informatics and Telecommunications

Πληροφορική

Πληροφορική

2019-11-08

2019

THEODOROU NIKOLAOS

Βασίλειος Ζησιμόπουλος, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών

The Maximum Rooted Connected Expansion problem

English

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.

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.

Technology - Computer science

Prefetching, connected dominating set, expansion, ratio, maximum leaf

Yes

4

Yes

16

43