Skip to Main content Skip to Navigation
Conference papers

An extremal problem on trees and database theory

Abstract : We consider an extremal problem on labelled directed trees and applications to database theory. Among others, we will show explicit keysystems on an underlying set of size $n$, that cannot be represented by a database of less than $2^{n(1-c\cdot \log \log n / \log n)}$ rows.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184450
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 2:59:33 PM
Last modification on : Monday, December 28, 2020 - 10:22:04 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:14:26 AM

File

dmAE0158.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184450, version 1

Collections

Citation

Gyula O.H. Katona, Krisztián Tichler. An extremal problem on trees and database theory. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.293-298. ⟨hal-01184450⟩

Share

Metrics

Record views

371

Files downloads

822