Back to search

University of Patras

Τυχαίες συνδυαστικές δομές

Abstract

dc:description

This 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/25692

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

Efthymiou, Charilaos; Ευθυμίου, Χαρίλαος. Τυχαίες συνδυαστικές δομές. University of Patras, 2008. http://hdl.handle.net/10442/hedi/25692