Name
Abstract | ||
|---|---|---|
Let H be an r-uniform hypergraph satisfying deg(x) = D(1 + o(1)) for each vertex x is an element of V(H) and deg(x, y) = o(D) for each pair of vertices x, y is an element of V(H), where D-->infinity. Recently, J. Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least n/r(1 - o(1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via ''nibbles.'' Further, let T-alpha be the number of edges that the random greedy algorithm has to consider before yielding a packing of size [n/r .(1-alpha)]. We show that almost surely T(alpha)similar to(1/alpha)(r-1). n/r(r-1) as alpha-->0(+) holds. (C) 1996 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1996 | 3.0.CO;2-W" target="_self" class="small-link-text"10.1002/(SICI)1098-2418(199605)8:33.0.CO;2-W | Random Struct. Algorithms |
Keywords | Field | DocType |
greedy algorithm,branching process | Discrete mathematics,Combinatorics,Vertex (geometry),Hypergraph,Constraint graph,Infinity,Greedy algorithm,Almost surely,Branching process,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 3 | 1042-9832 |
Citations | PageRank | References |
17 | 1.84 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vojtěch Rödl | 1 | 887 | 142.68 |
| Lubos Thoma | 2 | 42 | 5.34 |