The Library
Sharp thresholds for Hamiltonicity in random intersection graphs
Tools
Efthymiou, Charilaos and Spirakis, Paul G. (2010) Sharp thresholds for Hamiltonicity in random intersection graphs. Theoretical Computer Science, Vol.411 (No.40-42). pp. 3714-3730. doi:10.1016/j.tcs.2010.06.022 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2010.06.022
Abstract
Random Intersection Graphs, G(n,m,p), is a class of random graphs introduced in Karonski (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. Each element of the universal sets is chosen independently by some vertex with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m = inverted right perpendicularn(alpha)inverted left perpendicular, for any real alpha different than one, we establish here, for the first time, a sharp threshold for the graph property "Contains a Hamilton cycle". Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model. (C) 2010 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 6 September 2010 | ||||
Dates: |
|
||||
Volume: | Vol.411 | ||||
Number: | No.40-42 | ||||
Number of Pages: | 17 | ||||
Page Range: | pp. 3714-3730 | ||||
DOI: | 10.1016/j.tcs.2010.06.022 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Version or Related Resource: | A preliminary version of this work was presented at ICALP 2005, Efthymiou and Spirakis (2005) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |