Compressed subsequence matching and packed tree coloring

DOI10.1007/978-3-319-07566-2_5zbMath1359.68331arXiv1403.1065OpenAlexW2132841370WikidataQ60554325 ScholiaQ60554325MaRDI QIDQ513266

Patrick Hagge Cording, Philip Bille, Inge Li Gørtz

Publication date: 3 March 2017

Published in: Algorithmica, Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.1065

zbMATH Keywords

SLPcompressed subsequence matchingfirst colored ancestorstraight-line programtree coloring

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Data structures (68P05) Algorithms on strings (68W32)

Related Items (5)

Access, Rank, and Select in Grammar-compressed Strings ⋮ The nearest colored node in a tree ⋮ Succinct data structures for nearest colored node in a tree ⋮ Finger search in grammar-compressed strings ⋮ Balancing straight-line programs for strings and trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal on-line decremental connectivity in trees
• The level ancestor problem simplified
• Faster subsequence recognition in compressed strings
• Multiple serial episodes matching
• Surpassing the information theoretic bound with fusion trees
• Finding level-ancestors in trees
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Directed acyclic subsequence graph -- overview
• A data structure for dynamic trees
• Searching subsequences
• Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition
• Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts
• Window Subsequence Problems for Compressed Texts
• The Smallest Grammar Problem
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
• Minimizing diameters of dynamic trees
• Efficient dynamic method-lookup for object oriented languages
• Compact Labeling Scheme for Ancestor Queries
• Window-accumulated subsequence matching problem is linear

This page was built for publication: Compressed subsequence matching and packed tree coloring