On the complexity of recognizing Wheeler graphs
type: Item
instance of: scholarly article
title: On the complexity of recognizing Wheeler graphs
author: Daniel Gibney
author: Sharma V. Thankachan
published in: Algorithmica
publication date: 2022-03-22T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7495496
zbMATH Keywords: Wheeler graphs
zbMATH Keywords: FM-index
zbMATH Keywords: Burrows-Wheeler transform
MaRDI profile type: Publication
full work available at URL: s00453-021-00917-5
OpenAlex ID: W4206480194
cites work: Efficient string matching
cites work: Regular Languages meet Prefix Sorting
cites work: Wheeler languages
cites work: Succinct Dictionary Matching with No Slowdown
cites work: Succinct de Bruijn Graphs
cites work: A fixed-parameter algorithm for the directed feedback vertex set problem
cites work: A linear algorithm for embedding planar graphs using PQ-trees
cites work: Q5834367
cites work: Q4667610
cites work: Q5091210
cites work: Compressing and indexing labeled trees, with applications
cites work: Indexing compressed text
cites work: The compressed permuterm index
cites work: Wheeler graphs: a framework for BWT-based data structures
cites work: pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
cites work: On the Hardness and Inapproximability of Recognizing Wheeler Graphs
cites work: Planarity Algorithms via PQ-Trees (Extended Abstract)
cites work: Stack and Queue Layouts of Directed Acyclic Graphs: Part II
cites work: Stack and Queue Layouts of Directed Acyclic Graphs: Part I
cites work: Laying Out Graphs Using Queues
cites work: Faster compressed dictionary matching
cites work: Breakpoint Distance and PQ-Trees
cites work: Combinatorial Pattern Matching
cites work: An extension of the Burrows-Wheeler transform
cites work: Graph isomorphism, general remarks
cites work: Total Ordering Problem
DOI: 10.1007/S00453-021-00917-5
description: scientific article; zbMATH DE number 7495496