Geodesic
Finding Hamilton cycles in random intersection graphs
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2018_20_1_a9,
     author = {Rybarczyk, Katarzyna},
     title = {Finding {Hamilton} cycles in random intersection graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-8/}
}
TY  - JOUR
AU  - Rybarczyk, Katarzyna
TI  - Finding Hamilton cycles in random intersection graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-8/
DO  - 10.23638/DMTCS-20-1-8
LA  - en
ID  - DMTCS_2018_20_1_a9
ER  - 
%0 Journal Article
%A Rybarczyk, Katarzyna
%T Finding Hamilton cycles in random intersection graphs
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-8/
%R 10.23638/DMTCS-20-1-8
%G en
%F DMTCS_2018_20_1_a9
Rybarczyk, Katarzyna. Finding Hamilton cycles in random intersection graphs. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi: 10.23638/DMTCS-20-1-8

Cité par Sources :