Complexity issues of string to graph approximate matching

DOI10.1007/978-3-030-40608-0_17zbMath1437.68208arXiv2001.01961OpenAlexW3011130551MaRDI QIDQ782580

Giancarlo Mauri, Riccardo Dondi, Italo Zoppis

Publication date: 27 July 2020

Full work available at URL: https://arxiv.org/abs/2001.01961

zbMATH Keywords

computational complexitypatternsparameterized complexityalgorithms on stringsgraph querystring-to-graph matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

The complexity of approximate pattern matching on de Bruijn graphs ⋮ On the complexity of approximately matching a string to a directed graph

This page was built for publication: Complexity issues of string to graph approximate matching