Arboricity : an acyclic hypergraph decomposition problem motivated by database theory
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/99517 http://hdl.handle.net/10220/10864 |
| _version_ | 1826124720132587520 |
|---|---|
| author | Chee, Yeow Meng Ji, Lijun Lim, Andrew Tung, Anthony K. H. |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Chee, Yeow Meng Ji, Lijun Lim, Andrew Tung, Anthony K. H. |
| author_sort | Chee, Yeow Meng |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T06:24:59Z |
| format | Journal Article |
| id | ntu-10356/99517 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:24:59Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/995172020-03-07T12:34:47Z Arboricity : an acyclic hypergraph decomposition problem motivated by database theory Chee, Yeow Meng Ji, Lijun Lim, Andrew Tung, Anthony K. H. School of Physical and Mathematical Sciences 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. 2013-07-01T06:55:42Z 2019-12-06T20:08:17Z 2013-07-01T06:55:42Z 2019-12-06T20:08:17Z 2011 2011 Journal Article 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. 0166-218X https://hdl.handle.net/10356/99517 http://hdl.handle.net/10220/10864 10.1016/j.dam.2011.08.024 en Discrete applied mathematics © 2011 Elsevier B.V. |
| spellingShingle | Chee, Yeow Meng Ji, Lijun Lim, Andrew Tung, Anthony K. H. Arboricity : an acyclic hypergraph decomposition problem motivated by database theory |
| title | Arboricity : an acyclic hypergraph decomposition problem motivated by database theory |
| title_full | Arboricity : an acyclic hypergraph decomposition problem motivated by database theory |
| title_fullStr | Arboricity : an acyclic hypergraph decomposition problem motivated by database theory |
| title_full_unstemmed | Arboricity : an acyclic hypergraph decomposition problem motivated by database theory |
| title_short | Arboricity : an acyclic hypergraph decomposition problem motivated by database theory |
| title_sort | arboricity an acyclic hypergraph decomposition problem motivated by database theory |
| url | https://hdl.handle.net/10356/99517 http://hdl.handle.net/10220/10864 |
| work_keys_str_mv | AT cheeyeowmeng arboricityanacyclichypergraphdecompositionproblemmotivatedbydatabasetheory AT jilijun arboricityanacyclichypergraphdecompositionproblemmotivatedbydatabasetheory AT limandrew arboricityanacyclichypergraphdecompositionproblemmotivatedbydatabasetheory AT tunganthonykh arboricityanacyclichypergraphdecompositionproblemmotivatedbydatabasetheory |