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.
WEB OF SCIENCETM
checked on Sep 17, 2019
checked on Sep 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.