License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.18
URN: urn:nbn:de:0030-drops-86901
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8690/
Go to the corresponding LIPIcs Volume Portal

Chikhi, Rayan ; Schönhuth, Alexander

Dualities in Tree Representations

pdf-format:
LIPIcs-CPM-2018-18.pdf (0.5 MB)

Abstract

A characterization of the tree T^* such that BP(T^*)=ova{DFUDS(T)}, the reversal of DFUDS(T) is given. An immediate consequence is a rigorous characterization of the tree T^ such that BP(T^)=DFUDS(T). In summary, BP and DFUDS are unified within an encompassing framework, which might have the potential to imply future simplifications with regard to queries in BP and/or DFUDS. Immediate benefits displayed here are to identify so far unnoted commonalities in most recent work on the Range Minimum Query problem, and to provide improvements for the Minimum Length Interval Query problem.

BibTeX - Entry

@InProceedings{chikhi_et_al:LIPIcs:2018:8690,
  author =	{Rayan Chikhi and Alexander Sch{\"o}nhuth},
  title =	{{Dualities in Tree Representations}},
  booktitle =	{Annual Symposium on Combinatorial Pattern Matching  (CPM 2018)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Gonzalo Navarro and David Sankoff and Binhai Zhu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8690},
  URN =		{urn:nbn:de:0030-drops-86901},
  doi =		{10.4230/LIPIcs.CPM.2018.18},
  annote =	{Keywords: Data Structures, Succinct Tree Representation, Balanced Parenthesis Representation, Isomorphisms}
}

Keywords: Data Structures, Succinct Tree Representation, Balanced Parenthesis Representation, Isomorphisms
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI