On the complexity of recognizing Wheeler graphs

DOI10.1007/S00453-021-00917-5OpenAlexW4206480194MaRDI QIDQ2118211FDOQ2118211

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

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.

zbMATH Keywords

Burrows-Wheeler transformFM-indexWheeler graphs

Mathematics Subject Classification ID

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

Cites Work

• Efficient string matching
• A linear algorithm for embedding planar graphs using PQ-trees
• 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
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Title not available (Why is that?)
• Laying Out Graphs Using Queues
• Total Ordering Problem
• Title not available (Why is that?)
• Combinatorial Pattern Matching
• Faster compressed dictionary matching
• An extension of the Burrows-Wheeler transform
• Succinct Dictionary Matching with No Slowdown
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Graph isomorphism, general remarks
• Wheeler graphs: a framework for BWT-based data structures
• Title not available (Why is that?)
• Regular Languages meet Prefix Sorting
• pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
• Succinct de Bruijn Graphs
• Wheeler languages
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Breakpoint Distance and PQ-Trees
• Planarity Algorithms via PQ-Trees (Extended Abstract)

Cited In (5)

• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Wheeler graphs: a framework for BWT-based data structures
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Quantum time complexity and algorithms for pattern matching on labeled graphs

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)