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

Περίληψη

Η παρούσα διατριβή εστιάζει στα δίκτυα περιεχομένου. Τα δίκτυα αυτά μοντελοποιούνται με τη βοήθεια της θεωρίας γράφων και μελετώνται αλγόριθμοι που αφορούν στην διανομή περιεχομένου στους κόμβους τους και στην υποδομή τους. Σε σχέση με την υποδομή των δικτύων περιεχομένου, μελετάται το πρόβλημα της συντήρησης του δένδρου επικάλυψης ελαχίστου κόστους σε κατεθυνόμενους γράφους οι οποίοι υπόκεινται σε εισαγωγές και διαγραφές ακμών. H διανομή περιεχομένου μελετάται υπό δύο διαφορετικές οπτικές. Η πρώτη προϋποθέτει την ύπαρξη μιας εξωτερικής οντότητας, η οποία αποφασίζει σε ποιους κόμβους θα τοποθετηθούν ποια δεδομένα, με στόχο την ελαχιστοποίηση του συνολικού κόστους πρόσβασης από όλους τους αιτούντες. Εστιάζοντας σε δίκτυα όπου το πλήθος των κόμβων είναι σταθερό, προτείνονται βέλτιστοι αλγόριθμοι οι οποίοι αποφασίζουν τοποθετήσεις, ώστε το συνολικό κόστος πρόσβασης να είναι ελάχιστο. Οι αλγόριθμοι αυτοί συνιστούν την πρώτη ερευνητική προσπάθεια σε δίκτυα στα οποία οι τοπολογίες δεν είναι ...
περισσότερα

Περίληψη σε άλλη γλώσσα

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 ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/18685
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/18685
ND
18685
Εναλλακτικός τίτλος
Static and dynamic graph algorithms with applications to infrastructure and content replication in modern networks
Συγγραφέας
Πολλάτος, Γεράσιμος του Γ.
Ημερομηνία
2010
Ίδρυμα
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Σχολή Θετικών Επιστημών. Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Εξεταστική επιτροπή
Ζησιμόπουλος Βασίλειος
Κουτσουπιάς Ηλίας
Κολλιόπουλος Σταύρος
Σταυρακάκης Ιωάννης
Μήλης Ιωάννης
Φωτάκης Δημήτριος
Ξενάκης Χρήστος
Επιστημονικό πεδίο
Φυσικές ΕπιστήμεςΕπιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Λέξεις-κλειδιά
Δυναμικός προγραμματισμός; Nash ισορροπία; Δένδρο επικάλυψης; Τίμημα της αναρχίας
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
118 σ., εικ., ευρ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.