Tight bounds for top tree compression

Philip Bille, Finn Fernstrøm, Inge Li Gørtz

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We consider compressing labeled, ordered and rooted trees using DAG compression and top tree compression. We show that there exists a family of trees such that the size of the DAG compression is always a logarithmic factor smaller than the size of the top tree compression (even for an alphabet of size 1). The result settles an open problem from Bille et al. (Inform. and Comput., 2015).
Original languageEnglish
Title of host publicationString Processing and Information Retrieval
PublisherSpringer
Publication date2017
Pages97-102
DOIs
Publication statusPublished - 2017
Event24th International Symposium on String Processing and Information Retrieval, SPIRE 2017 - Palermo, Italy
Duration: 26 Sep 201729 Sep 2017
Conference number: 24
https://link.springer.com/book/10.1007/978-3-319-67428-5

Conference

Conference24th International Symposium on String Processing and Information Retrieval, SPIRE 2017
Number24
Country/TerritoryItaly
CityPalermo
Period26/09/201729/09/2017
Internet address
SeriesLecture Notes in Computer Science
Volume10508
ISSN0302-9743

Cite this