Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.dam.2011.08.024
Title: Arboricity: An acyclic hypergraph decomposition problem motivated by database theory
Authors: Chee, Y.M.
Ji, L.
Lim, A.
Tung, A.K.H. 
Keywords: Acyclic database schema
Acyclic hypergraph
Arboricity
Hypergraph decomposition
Packing
Steiner quadruple system
Steiner triple system
Issue Date: 2012
Source: 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) [20] 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.

Page view(s)

55
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.