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

(10)

• A new class of string transformations for compressed text indexing
• Co-lexicographically ordering automata and regular languages. I
• Finding an optimal alphabet ordering for Lyndon factorization is hard
• Edit and alphabet-ordering sensitivity of lex-parse
• Efficient construction of the BWT for repetitive text using string compression
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Efficient k-mer dataset compression using Eulerian covers of de Bruijn graphs and BWT
• Breaking a barrier in constructing compact indexes for parameterized pattern matching
• Minimizing the minimizers via alphabet reordering
• A class of heuristics for reducing the number of BWT-runs in the string ordering problem

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)