On the complexity of approximately matching a string to a directed graph
type: Item
instance of: scholarly article
title: On the complexity of approximately matching a string to a directed graph
zbMATH Open document ID: 1498.68202
author: Riccardo Dondi
author: Italo Zoppis
author: Giancarlo Mauri
published in: Information and Computation
publication date: 2022-10-13T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 7601278
MaRDI profile type: Publication
full work available at URL: j.ic.2021.104748
OpenAlex ID: W3159529122
cites work: Color-coding
cites work: Pattern Matching in Hypertext
cites work: On problems without polynomial kernels
cites work: Kernel bounds for path and cycle problems
cites work: Complexity issues of string to graph approximate matching
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Fundamentals of parameterized complexity
cites work: Q5091210
cites work: Q4198056
cites work: On the complexity of sequence to graph alignment
cites work: Improved approximate pattern matching on hypertext
cites work: Q5710169
cites work: Non deterministic polynomial optimization problems and their approximations
cites work: An Eulerian path approach to DNA fragment assembly
cites work: The Design of Approximation Algorithms
DOI: 10.1016/J.IC.2021.104748
description: scientific article; zbMATH DE number 7601278