Arboricity: An acyclic hypergraph decomposition problem motivated by database theory

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

doi:10.1016/j.dam.2011.08.024

Arboricity: An acyclic hypergraph decomposition problem motivated by database theory

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

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

5 Citations (Scopus)

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.

Original language	English
Pages (from-to)	100-107
Journal	Discrete Applied Mathematics
Volume	160
Issue number	1-2
DOIs	https://doi.org/10.1016/j.dam.2011.08.024
Publication status	Published - Jan 2012

Research Keywords

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

Access Output

10.1016/j.dam.2011.08.024Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{ff52ec4a199a4bd1a59248c931f668b1,

title = "Arboricity: An acyclic hypergraph decomposition problem motivated by database theory",

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. {\textcopyright} 2011 Elsevier B.V. All rights reserved.",

keywords = "Acyclic database schema, Acyclic hypergraph, Arboricity, Hypergraph decomposition, Packing, Steiner quadruple system, Steiner triple system",

author = "Chee, {Yeow Meng} and Lijun Ji and Andrew Lim and Tung, {Anthony K.H.}",

year = "2012",

month = jan,

doi = "10.1016/j.dam.2011.08.024",

language = "English",

volume = "160",

pages = "100--107",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Arboricity

T2 - An acyclic hypergraph decomposition problem motivated by database theory

AU - Chee, Yeow Meng

AU - Ji, Lijun

AU - Lim, Andrew

AU - Tung, Anthony K.H.

PY - 2012/1

Y1 - 2012/1

N2 - 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.

AB - 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.

KW - Acyclic database schema

KW - Acyclic hypergraph

KW - Arboricity

KW - Hypergraph decomposition

KW - Packing

KW - Steiner quadruple system

KW - Steiner triple system

UR - http://www.scopus.com/inward/record.url?scp=82755189283&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-82755189283&origin=recordpage

U2 - 10.1016/j.dam.2011.08.024

DO - 10.1016/j.dam.2011.08.024

M3 - RGC 21 - Publication in refereed journal

SN - 0166-218X

VL - 160

SP - 100

EP - 107

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-2

ER -

Arboricity: An acyclic hypergraph decomposition problem motivated by database theory

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this