Arboricity : An acyclic hypergraph decomposition problem motivated by database theory
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 100-107 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 160 |
Issue number | 1-2 |
Publication status | Published - Jan 2012 |
Link(s)
Abstract
The arboricity of a hypergraph H is the minimum number of acyclic hypergraphs that partition H. The determination of the arboricity of hypergraphs is a problem motivated by database theory. The exact arboricity of the complete k-uniform hypergraph of order n is previously known only for k∈1,2,n-2,n-1,n. The arboricity of the complete k-uniform hypergraph of order n is determined asymptotically when k=n-O(log1-δn), δ positive, and determined exactly when k=n-3. This proves a conjecture of Wang (2008) [20] in the asymptotic sense. © 2011 Elsevier B.V. All rights reserved.
Research Area(s)
- Acyclic database schema, Acyclic hypergraph, Arboricity, Hypergraph decomposition, Packing, Steiner quadruple system, Steiner triple system
Citation Format(s)
Arboricity: An acyclic hypergraph decomposition problem motivated by database theory. / Chee, Yeow Meng; Ji, Lijun; Lim, Andrew et al.
In: Discrete Applied Mathematics, Vol. 160, No. 1-2, 01.2012, p. 100-107.
In: Discrete Applied Mathematics, Vol. 160, No. 1-2, 01.2012, p. 100-107.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review