On the complexity of recognizing Wheeler graphs

DOI10.1007/S00453-021-00917-5MaRDI QIDQ2118211zbMATH OpenOpenAlexFDO

Authors Daniel Gibney, Sharma V. Thankachan

Publication date 22 March 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-021-00917-5

zbMATH Keywords

Burrows-Wheeler transformFM-indexWheeler graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• Wheeler languages
• Wheeler graphs: a framework for BWT-based data structures
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• scientific article; zbMATH DE number 2044948
• Recognizing DNA graphs is difficult.

Cites work

• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 7561548 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A linear algorithm for embedding planar graphs using PQ-trees
• An extension of the Burrows-Wheeler transform
• Breakpoint Distance and PQ-Trees
• Combinatorial Pattern Matching
• Compressing and indexing labeled trees, with applications
• Efficient string matching
• Faster compressed dictionary matching
• Graph isomorphism, general remarks
• Indexing compressed text
• Laying Out Graphs Using Queues
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Planarity algorithms via PQ-trees (extended abstract)
• Regular Languages meet Prefix Sorting
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Succinct Dictionary Matching with No Slowdown
• Succinct de Bruijn graphs
• The compressed permuterm index
• Total Ordering Problem
• Wheeler graphs: a framework for BWT-based data structures
• Wheeler languages
• pBWT: achieving succinct data structures for parameterized pattern matching and related problems

Cited in

(16)

• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Wheeler languages
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Wheeler graphs: a framework for BWT-based data structures
• Prefix-free parsing for building large tunnelled Wheeler graphs
• Algorithms and complexity on indexing founder graphs
• Co-lexicographically ordering automata and regular languages. I
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• On the complexity of computing the co-lexicographic width of a regular language
• Completing Wheeler automata
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• Random Wheeler automata
• Ordering regular languages and automata: complexity
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• On representing the degree sequences of sublogarithmic-degree Wheeler graphs
• Optimal Wheeler language recognition

This page was built for publication: On the complexity of recognizing Wheeler graphs

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