Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/99517
Title: Arboricity : an acyclic hypergraph decomposition problem motivated by database theory
Authors: Chee, Yeow Meng
Ji, Lijun
Lim, Andrew
Tung, Anthony K. H.
Issue Date: 2011
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.
Series/Report no.: Discrete applied mathematics
Abstract: The arboricity of a hypergraph HH is the minimum number of acyclic hypergraphs that partition HH. The determination of the arboricity of hypergraphs is a problem motivated by database theory. The exact arboricity of the complete kk-uniform hypergraph of order nn is previously known only for k∈{1,2,n−2,n−1,n}k∈{1,2,n−2,n−1,n}. The arboricity of the complete kk-uniform hypergraph of order nn is determined asymptotically when k=n−O(log1−δn)k=n−O(log1−δn), δδ positive, and determined exactly when k=n−3k=n−3. This proves a conjecture of Wang (2008) [20] in the asymptotic sense.
URI: https://hdl.handle.net/10356/99517
http://hdl.handle.net/10220/10864
ISSN: 0166-218X
DOI: http://dx.doi.org/10.1016/j.dam.2011.08.024
Rights: © 2011 Elsevier B.V.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.