Please use this identifier to cite or link to this item:
|Title:||Arboricity: An acyclic hypergraph decomposition problem motivated by database theory||Authors:||Chee, Y.M.
|Keywords:||Acyclic database schema
Steiner quadruple system
Steiner triple system
|Issue Date:||2012||Citation:||Chee, Y.M., Ji, L., Lim, A., Tung, A.K.H. (2012). Arboricity: An acyclic hypergraph decomposition problem motivated by database theory. Discrete Applied Mathematics 160 (1-2) : 100-107. ScholarBank@NUS Repository. https://doi.org/10.1016/j.dam.2011.08.024||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(log 1-δn), δ positive, and determined exactly when k=n-3. This proves a conjecture of Wang (2008)  in the asymptotic sense. © 2011 Elsevier B.V. All rights reserved.||Source Title:||Discrete Applied Mathematics||URI:||http://scholarbank.nus.edu.sg/handle/10635/39445||ISSN:||0166218X||DOI:||10.1016/j.dam.2011.08.024|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 25, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.