Finding Hamilton cycles in random intersection graphs
From MaRDI portal
Abstract: The construction of the random intersection graph model is based on a random family of sets. Such structures, which are derived from intersections of sets, appear in a natural manner in many applications. In this article we study the problem of finding a Hamilton cycle in a random intersection graph. To this end we analyse a classical algorithm for finding Hamilton cycles in random graphs (algorithm HAM) and study its efficiency on graphs from a family of random intersection graphs (denoted here by G(n,m,p)). We prove that the threshold function for the property of HAM constructing a Hamilton cycle in G(n,m,p) is the same as the threshold function for the minimum degree at least two. Until now, known algorithms for finding Hamilton cycles in G(n,m,p) were designed to work in very small ranges of parameters and, unlike HAM, used the structure of the family of random sets.
Recommendations
Cited in
(8)- On Hamiltonicity of uniform random intersection graphs
- Automata, Languages and Programming
- Algorithms and Computation
- Finding tight Hamilton cycles in random hypergraphs faster
- A note on hamiltonicity of uniform random intersection graphs
- An algorithm for finding Hamilton paths and cycles in random graphs
- Hamilton cycles in the line graph of a random graph
- Sharp thresholds for Hamiltonicity in random intersection graphs
This page was built for publication: Finding Hamilton cycles in random intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4560230)
