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

Στη διπλωματική αυτή εργασία ορίζουμε δυο νέα μοντέλα τυχαίων γραφημάτων τομής ετικετών και εξετάζονται ως προς ορισμένες σημαντικές γραφοθεωρητικές ιδιότητές τους. Ένα τυχαίο γράφημα τομής ετικετών παράγεται αντιστοιχώντας σε κάθε κορυφή ένα \\\\emph{τυχαίο} υποσύνολο ενός πεπερασμένου) σύμπαντος $...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας: Ραπτόπουλος, Χριστόφορος
Άλλοι συγγραφείς: Νικολετσέας, Σωτήρης
Έκδοση: 2007
Θέματα:
Διαθέσιμο Online:http://nemertes.lis.upatras.gr/jspui/handle/10889/155
id nemertes-10889-155
record_format dspace
institution UPatras
collection Nemertes
topic Τυχαίο Γράφημα Τομής
Πιθανοτικός αλγόριθμος
Ανεξάρτητο σύνολο κορυφών
Random Intersection Graph
Randomized algorithm
Independent set
005.1
spellingShingle Τυχαίο Γράφημα Τομής
Πιθανοτικός αλγόριθμος
Ανεξάρτητο σύνολο κορυφών
Random Intersection Graph
Randomized algorithm
Independent set
005.1
Ραπτόπουλος, Χριστόφορος
Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής
description Στη διπλωματική αυτή εργασία ορίζουμε δυο νέα μοντέλα τυχαίων γραφημάτων τομής ετικετών και εξετάζονται ως προς ορισμένες σημαντικές γραφοθεωρητικές ιδιότητές τους. Ένα τυχαίο γράφημα τομής ετικετών παράγεται αντιστοιχώντας σε κάθε κορυφή ένα \\\\emph{τυχαίο} υποσύνολο ενός πεπερασμένου) σύμπαντος $M$ από $m$ στοιχεία και βάζοντας μια ακμή μεταξύ δυο κορυφών αν και μόνον εάν τα αντίστοιχα σύνολά τους έχουν μη κενή τομή. Συγκεκριμενοποιώντας την κατανομή που ακολουθεί το τυχαίο υποσύνολο που αντιστοιχείται σε κάθε κορυφή παίρνουμε διαφορετικά μοντέλα τυχαίων γραφημάτων τομής. Στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής κάθε στοιχείο $i$ του $M$ επιλέγεται ανεξάρτητα από κάθε κορυφή με πιθανότητα $p_i$. Το ομοιόμορφο μοντέλο τυχαίων γραφημάτων τομής ετικετών αποτελεί μια ειδική περίπτωση του γενικευμένου μοντέλου όπου η πιθανότητα επιλογής των στοιχείων του $M$ είναι ίση με $p$, δηλαδή ίδια για όλα τα στοιχεία του $M$. Όπως θα δούμε, για ορισμένες τιμές των παραμέτρων $m$ και $p$, το ομοιόμορφο μοντέλο είναι ισοδύναμο με το μοντέλο $G_{n, \\\\hat{p}}$, δηλαδή με το μοντέλο τυχαίων γραφημάτων στο οποίο κάθε πλευρά εμφανίζεται στοχαστικά ανεξάρτητα με πιθανότητα $\\\\hat{p}$. Τέλος, στο κανονικό μοντέλο τυχαίων γραφημάτων τομής ετικετών το υποσύνολο του $M$ που αντιστοιχείται σε κάθε κορυφή έχει σταθερό αριθμό στοιχείων. Λόγω της στοχαστικής εξάρτησης που υποννοείται για την ύπαρξη πλευρών, τα γραφήματα αυτά θεωρούνται αρκετά ρεαλιστικά μοντέλα (σε σχέση με τα κλασσικά τυχαία γραφήματα) σε πολλές πρακτικές εφαρμογές, ιδιαίτερα σε αλγοριθμικά θέματα δικτύων. Στην εργασία αυτή αρχικά παρουσιάζουμε μερικά χαρακτηριστικά αποτελέσματα από τη σχετική βιβλιογραφία για τα μοντέλα αυτά. Ακόμα, μελετάμε, για πρώτη φορά στη βιβλιογραφία, την ύπαρξη ανεξάρτητων συνόλων κορυφών μεγέθους $k$ στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής ετικετών, υπολογίζοντας τη μέση τιμή και τη διασπορά του αριθμού τους. Επίσης, προτείνουμε και αναλύουμε τρείς πιθανοτικούς αλγόριθμους που τρέχουν σε μικρό πολυωνυμικό χρόνο (ως προς τον αριθμό των κορυφών και τον αριθμό των στοιχείων του $M$) για την εύρεση αρκετά μεγάλων συνόλων ανεξάρτητων κορυφών.
author2 Νικολετσέας, Σωτήρης
author_facet Νικολετσέας, Σωτήρης
Ραπτόπουλος, Χριστόφορος
author Ραπτόπουλος, Χριστόφορος
author_sort Ραπτόπουλος, Χριστόφορος
title Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής
title_short Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής
title_full Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής
title_fullStr Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής
title_full_unstemmed Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής
title_sort σχεδιασμός και ανάλυση αλγορίθμων σε τυχαία γραφήματα τομής
publishDate 2007
url http://nemertes.lis.upatras.gr/jspui/handle/10889/155
work_keys_str_mv AT raptopouloschristophoros schediasmoskaianalysēalgorithmōnsetychaiagraphēmatatomēs
AT raptopouloschristophoros designandanalysisofalgorithmsonrandomintersectiongraphs
_version_ 1771297147482800128
spelling nemertes-10889-1552022-09-05T05:37:34Z Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής Design and analysis of algorithms on Random Intersection Graphs Ραπτόπουλος, Χριστόφορος Νικολετσέας, Σωτήρης Νικολετσέας, Σωτήρης Σπιράκης, Παύλος Κακλαμάνης, Χρήστος Raptopoulos, Christoforos Τυχαίο Γράφημα Τομής Πιθανοτικός αλγόριθμος Ανεξάρτητο σύνολο κορυφών Random Intersection Graph Randomized algorithm Independent set 005.1 Στη διπλωματική αυτή εργασία ορίζουμε δυο νέα μοντέλα τυχαίων γραφημάτων τομής ετικετών και εξετάζονται ως προς ορισμένες σημαντικές γραφοθεωρητικές ιδιότητές τους. Ένα τυχαίο γράφημα τομής ετικετών παράγεται αντιστοιχώντας σε κάθε κορυφή ένα \\\\emph{τυχαίο} υποσύνολο ενός πεπερασμένου) σύμπαντος $M$ από $m$ στοιχεία και βάζοντας μια ακμή μεταξύ δυο κορυφών αν και μόνον εάν τα αντίστοιχα σύνολά τους έχουν μη κενή τομή. Συγκεκριμενοποιώντας την κατανομή που ακολουθεί το τυχαίο υποσύνολο που αντιστοιχείται σε κάθε κορυφή παίρνουμε διαφορετικά μοντέλα τυχαίων γραφημάτων τομής. Στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής κάθε στοιχείο $i$ του $M$ επιλέγεται ανεξάρτητα από κάθε κορυφή με πιθανότητα $p_i$. Το ομοιόμορφο μοντέλο τυχαίων γραφημάτων τομής ετικετών αποτελεί μια ειδική περίπτωση του γενικευμένου μοντέλου όπου η πιθανότητα επιλογής των στοιχείων του $M$ είναι ίση με $p$, δηλαδή ίδια για όλα τα στοιχεία του $M$. Όπως θα δούμε, για ορισμένες τιμές των παραμέτρων $m$ και $p$, το ομοιόμορφο μοντέλο είναι ισοδύναμο με το μοντέλο $G_{n, \\\\hat{p}}$, δηλαδή με το μοντέλο τυχαίων γραφημάτων στο οποίο κάθε πλευρά εμφανίζεται στοχαστικά ανεξάρτητα με πιθανότητα $\\\\hat{p}$. Τέλος, στο κανονικό μοντέλο τυχαίων γραφημάτων τομής ετικετών το υποσύνολο του $M$ που αντιστοιχείται σε κάθε κορυφή έχει σταθερό αριθμό στοιχείων. Λόγω της στοχαστικής εξάρτησης που υποννοείται για την ύπαρξη πλευρών, τα γραφήματα αυτά θεωρούνται αρκετά ρεαλιστικά μοντέλα (σε σχέση με τα κλασσικά τυχαία γραφήματα) σε πολλές πρακτικές εφαρμογές, ιδιαίτερα σε αλγοριθμικά θέματα δικτύων. Στην εργασία αυτή αρχικά παρουσιάζουμε μερικά χαρακτηριστικά αποτελέσματα από τη σχετική βιβλιογραφία για τα μοντέλα αυτά. Ακόμα, μελετάμε, για πρώτη φορά στη βιβλιογραφία, την ύπαρξη ανεξάρτητων συνόλων κορυφών μεγέθους $k$ στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής ετικετών, υπολογίζοντας τη μέση τιμή και τη διασπορά του αριθμού τους. Επίσης, προτείνουμε και αναλύουμε τρείς πιθανοτικούς αλγόριθμους που τρέχουν σε μικρό πολυωνυμικό χρόνο (ως προς τον αριθμό των κορυφών και τον αριθμό των στοιχείων του $M$) για την εύρεση αρκετά μεγάλων συνόλων ανεξάρτητων κορυφών. In this Master thesis we define and analyse two new models of random intersection graphs. A random intersection graph is produced by assigning to each vertex a random subset of a (finite) universe $M$ of $m$ elements and by drawing an edge between two vertices if and only if their corresponding subsets have some elements in common. By specifying the distribution of the subsets assigned to each vertex, we get various models of random intersection graphs. In the generalized random intersection graphs model each element $i$ in $M$ is chosen independently with probability $p_i$. The uniform random intersection graphs model is a special case of the generalized model where the probability of selecting an element of $M$ is $p$, i.e. the same for every element. As we will see, for some range of values of the parameters $m$ and $p$, the uniform model is equivalent in some sense with the model $G_{n, \\\\hat{p}}$, i.e. the random graphs model in which each edge appears independently with probability $\\\\hat{p}$. Finally, in the regular random intersection graphs model, the subset of $M$ assigned to each vertex has a fixed number of elements. Due to the dependence implied in the appearance of edges, these models are considered to be more realistic (than classic random graphs) in many applications. This thesis begins by presenting several important results concearning these models. Also, we study for the first time the existence of independent sets of size $k$ in the generalized random intersection graphs model, and we give exact formulae for the mean and variance of their number. Additionally, we propose three randomized algorithms, that run in small polynomial time (with respect to the number of vertices and the number of elements of $M$), for finding large independent sets of vertices. 2007-05-16T11:16:47Z 2007-05-16T11:16:47Z 2005-09-09 2007-05-16T11:16:47Z http://nemertes.lis.upatras.gr/jspui/handle/10889/155 Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. application/pdf