Please use this identifier to cite or link to this item:
|Title:||Arboricity: An acyclic hypergraph decomposition problem motivated by database theory|
|Keywords:||Acyclic database schema|
Steiner quadruple system
Steiner triple system
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 13, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.