Name
Abstract | ||
|---|---|---|
Consider a universal set ${\cal M}$ and a vertex set V and suppose that to each vertex in V we assign independently a subset of ${\cal M}$ chosen at random according to some probability distribution over subsets of ${\cal M}$. By connecting two vertices if their assigned subsets have elements in common, we get a random instance of a random intersection graphs model. In this work, we overview some results concerning the existence and efficient construction of Hamilton cycles in random intersection graph models. In particular, we present and discuss results concerning two special cases where the assigned subsets to the vertices are formed by (a) choosing each element of ${\cal M}$ independently with probability p and (b) selecting uniformly at random a subset of fixed cardinality. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-24897-9_15 | Algebraic Foundations in Computer Science |
Keywords | Field | DocType |
assigned subsets,random instance,selected combinatorial property,hamilton cycle,random intersection graph model,cal m,efficient construction,probability p,universal set,probability distribution,random intersection graphs model | Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Hamiltonian path,Cardinality,Greedy algorithm,Intersection graph,Probability distribution,Mathematics,Universal set | Conference |
Volume | ISSN | Citations |
7020 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sotiris Nikoletseas | 1 | 839 | 70.52 |
| Christoforos Raptopoulos | 2 | 192 | 22.39 |
| Paul G. Spirakis | 3 | 2222 | 299.05 |