2018-05-01
Dualities in tree representations
Publication
Publication
Presented at the
Annual Symposium on Combinatorial Pattern Matching (July 2018), Qingdao, China
A characterization of the tree T∗ such that BP(T∗) = ↔ 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.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.4230/LIPIcs.CPM.2018.18 | |
| Leibniz International Proceedings in Informatics | |
| Annual Symposium on Combinatorial Pattern Matching | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Chikhi, R, & Schönhuth, A. (2018). Dualities in tree representations. In 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018 (pp. 18:1–18:12). doi:10.4230/LIPIcs.CPM.2018.18
|
|
