Geodesic
On random greedy triangle packing
The electronic journal of combinatorics, Tome 4 (1997) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The behaviour of the random greedy algorithm for constructing a maximal packing of edge-disjoint triangles on $n$ points (a maximal partial triple system) is analysed with particular emphasis on the final number of unused edges. It is shown that this number is at most $n^{7/4+o(1)}$, "halfway" from the previous best-known upper bound $o(n^2)$ to the conjectured value $n^{3/2+o(1)}$. The more general problem of random greedy packing in hypergraphs is also considered.
DOI : 10.37236/1296
Classification : 05B40, 05C70
Mots-clés : greedy algorithm, packing, triple system, packing hypergraphs 
@article{10_37236_1296,
     author = {David A. Grable},
     title = {On random greedy triangle packing},
     journal = {The electronic journal of combinatorics},
     year = {1997},
     volume = {4},
     number = {1},
     doi = {10.37236/1296},
     zbl = {0885.05051},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1296/}
}
TY  - JOUR
AU  - David A. Grable
TI  - On random greedy triangle packing
JO  - The electronic journal of combinatorics
PY  - 1997
VL  - 4
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1296/
DO  - 10.37236/1296
ID  - 10_37236_1296
ER  - 
%0 Journal Article
%A David A. Grable
%T On random greedy triangle packing
%J The electronic journal of combinatorics
%D 1997
%V 4
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1296/
%R 10.37236/1296
%F 10_37236_1296
David A. Grable. On random greedy triangle packing. The electronic journal of combinatorics, Tome 4 (1997) no. 1. doi: 10.37236/1296

Cité par Sources :