Back to search

National and Kapodistrian University of Athens

Στατικοί και δυναμικοί γραφοθεωρητικοί αλγόριθμοι με εφαρμογές στη διαχείριση της υποδομής και του περιεχομένου των σύγχρονων δικτύων

Abstract

dc:description

This 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 × 13

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/18685

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Pollatos, Gerasimos; Πολλάτος, Γεράσιμος. Στατικοί και δυναμικοί γραφοθεωρητικοί αλγόριθμοι με εφαρμογές στη διαχείριση της υποδομής και του περιεχομένου των σύγχρονων δικτύων. National and Kapodistrian University of Athens, 2010. http://hdl.handle.net/10442/hedi/18685