Arboricity: An acyclic hypergraph decomposition problem motivated by database theory
| Autor: | Lijun Ji, Anthony K. H. Tung, Yeow Meng Chee, Andrew Lim |
|---|---|
| Přispěvatelé: | School of Physical and Mathematical Sciences |
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Hypergraph Steiner triple system Mathematics::Combinatorics Conjecture Quantitative Biology::Neurons and Cognition Applied Mathematics Arboricity Hypergraph decomposition Packing Combinatorics Steiner quadruple system Steiner system Acyclic database schema Computer Science::Discrete Mathematics Discrete Mathematics and Combinatorics Partition (number theory) Database theory Acyclic hypergraph Computer Science::Distributed Parallel and Cluster Computing Decomposition problem Mathematics |
| Zdroj: | Discrete Applied Mathematics. 160:100-107 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2011.08.024 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect