On the complexity of recognizing Wheeler graphs

DOI10.1007/s00453-021-00917-5OpenAlexW4206480194MaRDI QIDQ2118211

Sharma V. Thankachan, Daniel Gibney

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)

Related Items (3)

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear algorithm for embedding planar graphs using PQ-trees
• Graph isomorphism, general remarks
• Wheeler graphs: a framework for BWT-based data structures
• Faster compressed dictionary matching
• Wheeler languages
• An extension of the Burrows-Wheeler transform
• The compressed permuterm index
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Compressing and indexing labeled trees, with applications
• Indexing compressed text
• Succinct Dictionary Matching with No Slowdown
• Breakpoint Distance and PQ-Trees
• Laying Out Graphs Using Queues
• Efficient string matching
• Total Ordering Problem
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
• Succinct de Bruijn Graphs
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Regular Languages meet Prefix Sorting
• Planarity Algorithms via PQ-Trees (Extended Abstract)
• Combinatorial Pattern Matching

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