National and Kapodistrian University of Athens
Στατικοί και δυναμικοί γραφοθεωρητικοί αλγόριθμοι με εφαρμογές στη διαχείριση της υποδομής και του περιεχομένου των σύγχρονων δικτύων
Abstract
dc:descriptionThis thesis focuses on content networks, which are modelled with the help of graph theory and for which various algorithms are studied concerning the infrastructure and the content replication. In terms of the infrastructure the fundamental problem of maintaining a directed minimum cost spanning tree is studied, when the underlying graph changes through insertions or deletions of edges. In terms of content replication two different approaches are studied. The first concerns centralized replication of content by an external authority so as the total access cost over all users is minimized. For the case of constant number of users, optimal algorithms are designed. These algorithms constitute the first attempt to cope with non-metric topologies. The second approaches is based on the fact that participants are autonomous and behave selfishly. By defining an appropriate non-cooperative strategic game, existence of pure Nash equilibria is studied and tight bound on the prices of anarchy and stability are provided.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2010
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Pollatos, Gerasimos
- Πολλάτος, Γεράσιμος
Subjects
dc:subject × 13Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/18685