scientific article; zbMATH DE number 7651154

DOI10.4230/LIPICS.ESA.2020.15MaRDI QIDQ5874481zbMATH OpenFDO

Authors Jason Bentley, Daniel Gibney, Sharma V. Thankachan

Publication date 7 February 2023

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

zbMATH Keywords

APX-hardnessNP-hardnessBWT

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• scientific article; zbMATH DE number 7559192 (Why is no real title available?)
• A faster implementation of online RLBWT and its application to LZ77 parsing
• A new class of searchable and provably highly compressible string transformations
• At the roots of dictionary compression: string attractors
• Block sorting-based transformations on words: beyond the magic BWT
• Combinatorial Pattern Matching
• Efficient construction of a complete index for pan-genomics read alignment
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Lower bounds based on the exponential time hypothesis
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• On the sorting-complexity of suffix tree construction
• Online LZ77 parsing and matching statistics with RLBWTs
• Optimal construction of compressed indexes for highly repetitive texts
• Optimization, approximation, and complexity classes
• Parameterized algorithms
• Regular Languages meet Prefix Sorting
• Storage and Retrieval of Individual Genomes
• The Traveling Salesman Problem with Distances One and Two
• Wheeler graphs: a framework for BWT-based data structures

Cited in

(3)

• A new class of string transformations for compressed text indexing
• Efficient construction of the BWT for repetitive text using string compression
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries

Describes a project that uses

Uses Software

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

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874481)