Quantum time complexity and algorithms for pattern matching on labeled graphs

DOI10.1007/978-3-031-20643-6_22zbMath1525.68063OpenAlexW4312791883MaRDI QIDQ6111593

Sharma V. Thankachan, Parisa Darbari, Daniel Gibney

Publication date: 4 August 2023

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-20643-6_22

zbMATH Keywords

quantum algorithmspattern matchinglabeled graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time
• Improved approximate pattern matching on hypertext
• Wheeler graphs: a framework for BWT-based data structures
• On the complexity of recognizing Wheeler graphs
• The complexity of approximate pattern matching on de Bruijn graphs
• Search via Quantum Walk
• Pattern Matching in Hypertext
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Regular Languages meet Prefix Sorting
• Quantum Query Complexity of Some Graph Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quantum time complexity and algorithms for pattern matching on labeled graphs