scientific article; zbMATH DE number 7651154

DOI10.4230/LIPIcs.ESA.2020.15MaRDI QIDQ5874481

Sharma V. Thankachan, Jason Bentley, Daniel Gibney

Publication date: 7 February 2023

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

NP-hardnessAPX-hardnessBWT

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

A new class of string transformations for compressed text indexing, Efficient construction of the BWT for repetitive text using string compression

Uses Software

• Soap
• BWA
• r-index
• Big-BWT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Block sorting-based transformations on words: beyond the magic BWT
• Wheeler graphs: a framework for BWT-based data structures
• A faster implementation of online RLBWT and its application to LZ77 parsing
• Efficient construction of a complete index for pan-genomics read alignment
• Storage and Retrieval of Individual Genomes
• The Traveling Salesman Problem with Distances One and Two
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• A new class of searchable and provably highly compressible string transformations
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• Online LZ77 Parsing and Matching Statistics with RLBWTs
• Regular Languages meet Prefix Sorting
• At the roots of dictionary compression: string attractors
• Optimal Construction of Compressed Indexes for Highly Repetitive Texts
• On the sorting-complexity of suffix tree construction
• Parameterized Algorithms
• Combinatorial Pattern Matching