On random greedy triangle packing
type: Item
instance of: scholarly article
title: On random greedy triangle packing
zbMATH Open document ID: 0885.05051
author: David A. Grable
published in: The Electronic Journal of Combinatorics
publication date: 1998-02-12T00:00:00Z
full work available at URL: https://eudml.org/doc/119246
full work available at URL: v4i1r11.html
review text: Summary: 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.
Mathematics Subject Classification ID: 05B40
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1117996
zbMATH Keywords: greedy algorithm
zbMATH Keywords: packing
zbMATH Keywords: triple system
zbMATH Keywords: packing hypergraphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1117996