Arboricity : An acyclic hypergraph decomposition problem motivated by database theory

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations

Author(s)

  • Yeow Meng Chee
  • Lijun Ji
  • Andrew Lim
  • Anthony K.H. Tung

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)100-107
Journal / PublicationDiscrete Applied Mathematics
Volume160
Issue number1-2
Publication statusPublished - Jan 2012

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(log1-δ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.

Research Area(s)

  • Acyclic database schema, Acyclic hypergraph, Arboricity, Hypergraph decomposition, Packing, Steiner quadruple system, Steiner triple system

Citation Format(s)

Arboricity: An acyclic hypergraph decomposition problem motivated by database theory. / Chee, Yeow Meng; Ji, Lijun; Lim, Andrew et al.
In: Discrete Applied Mathematics, Vol. 160, No. 1-2, 01.2012, p. 100-107.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review