On the complexity of approximately matching a string to a directed graph

DOI10.1016/j.ic.2021.104748zbMath1498.68202OpenAlexW3159529122MaRDI QIDQ2084771

Riccardo Dondi, Italo Zoppis, Giancarlo Mauri

Publication date: 13 October 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2021.104748

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)

On the Complexity of String Matching for Graphs ⋮ Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Kernel bounds for path and cycle problems
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Complexity issues of string to graph approximate matching
• On problems without polynomial kernels
• Non deterministic polynomial optimization problems and their approximations
• Improved approximate pattern matching on hypertext
• On the complexity of sequence to graph alignment
• The Design of Approximation Algorithms
• Color-coding
• An Eulerian path approach to DNA fragment assembly
• Pattern Matching in Hypertext

This page was built for publication: On the complexity of approximately matching a string to a directed graph