Abstract
dc:descriptionThis thesis can be partitioned into 2 parts regarding the subject: In the first part we study the following problem. For given n,m,p we investigate if an instance of random intersection graph G (n,m,p) contains or not a Hamilton cycle. We assume that the parameter p of the model is such that p=p (n,m). We show that for the range of n,m,p which the model is not trivial or equivalent to other models the graph property contains a Hamilton cycle, exhibits sharp threshold. In the second part of the thesis we deal with the problem of algorithmically estimating the size the set of proper k-colourings of an instance of sparse random graph G (n,p). We present a polynomial time algorithm which has the following properties. It has input an instance of sparse G (n,p) and an integer k. If k is greater than some quantity which depends on the average degree of the graph, then with high probability it returns a k-colouring of the input graph which is asymptotically equal to the uniform over the set of all k-colouring of the input graph. Trivially, the above algorithm we present allows to estimate the size of the set of all colouring of the input graph. This algorithm improves a previous one of Dyer et.al.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Efthymiou, Charilaos
- Ευθυμίου, Χαρίλαος
Subjects
dc:subject × 22- Τυχαίο γράφημα τομής
- Αραιό τυχαίο γράφημα
- Τυχαίος χρωματισμός
- Κύκλος Hamilton
- Κατώφλι
- Σύστημα Spin
- Δειγματοληψία
- Random intersection graph
- Sparse random graph
- Random colouring
- Hamilton cycle
- Threshold
- Spin system
- Sampling
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- 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/25692