University of Patras
Σχεδιασμός και ανάλυση αλγορίθμων για τυχαία και εξελικτικά δίκτυα
Abstract
dc:descriptionLet $V$ be a set of $i$ vertices and let ${\cal M}$ be a finite set of $m$ labels. An intersection graph is then constructed by assigning to each vertex $v \in V$ a subset Sv of ${\cal M}$ and then connecting every pair of vertices that have common labels in their corresponding label sets. This thesis concerns the study of combinatorial properties, as well as the design and analysis of algorithms on two kinds of random intersection graphs models that arise from different choices of the distribution that we use to construct the sets Sv. In the first of these models, called \emph{Random Intersection Graphs Model} {\cal G}n, m, p, each set of labels Sv is constructed by choosing independently each label with probability $p$. In the second model, called \emph{Uniform Random Intersection Graphs Model} {\cal G}n, m, \lambda, each label set Sv is selected equiprobably (and independently for each vertex $v$) among all subsets of ${\cal M}$ of size $\lambda$. These models can be used to abstract situations that concern the efficient and secure communication in sensor networks, but can also be used to model the conflicts that occur in oblivious resource sharing in distributed settings. Moreover, random intersection graph models can be used to model social graphs, in which two entities are connected when they have a common feature. In the Random Intersection Graphs Model {\cal G}n, m, p, we first study the existence and efficient construction of Hamilton cycles. More specifically, we give an upper bound for the probability $p$ that is needed for almost every random instance Gn, m, p of the model to have a Hamilton cycle. We also present two polynomial time, randomized algorithms for constructing Hamilton cycles in a wide range of the parameters $m, p$. Moreover, we show that almost every random instance of the {\cal G}n, m, p model is an expander, even for $p$ very close to the connectivity threshold. Finally, we give close to optimal bounds (that hold with probability that goes to 1 for a wide range of the parameters of the model) for important quantities (like the mixing time and the cover time) concerning random walks on random instances of {\cal G}n, m, p. In the Uniform Random Intersection Graphs Model {\cal G}n, m, \lambda we study the existence of Hamilton cycles for a ce rtain range of the parameters $m, \lambda$. Finally, by using the probabilistic method we compute the independence number of {\cal G}n, m, \lambda.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Raptopoulos, Christoforos
- Ραπτόπουλος, Χριστόφορος
Subjects
dc:subject × 23- Τυχαία γραφήματα τομής ετικετών
- Αλγόριθμοι, Πιθανοτικοί
- Ασυμπτωτική συμπεριφορά
- Πιθανοτική μέθοδος
- Στοχαστικές διεργασίες
- Κύκλοι hamilton
- Επεκτασιμότητα
- Τυχαίοι περίπατοι
- Random intersection graphs
- Asymptotic behaviour
- Probabilistic methods
- Stochastic processes
- Hamilton cycles
- Expansion
- Random walks
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/25727