Size-optimal top dag compression
| Autor: | Markus Lohrey, Carl Philipp Reh, Kurt Sieber |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0102 computer and information sciences
02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Combinatorics Tree (descriptive set theory) 010201 computation theory & mathematics Bounded function Compression (functional analysis) Signal Processing 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Node (circuits) Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 147:27-31 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2019.03.001 |
| Popis: | It is shown that for a given ordered node-labelled tree of size n and with s different node labels, one can construct in linear time a top dag of height O ( log n ) and size bounded by O ( n / log σ n ) and O ( d ⋅ log n ) , where σ = max { 2 , s } and d is the size of the minimal dag. The size bound O ( n / log σ n ) is optimal and improves on previous bounds. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect