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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/99517 http://hdl.handle.net/10220/10864 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|