IRIS – Institutional Research Information System
IRIS è il sistema di gestione della ricerca dell’Università degli Studi di Milano-Bicocca.Il repository BOA è il modulo del sistema dedicato alla raccolta e alla disseminazione della produzione scientifica di Ateneo. Le pubblicazioni sono ricercabili per parola chiave attraverso il box nella barra orizzontale in alto oppure, mediante il pulsante Sfoglia, per "Afferenza", "Autore", "Titolo", "Tipologia" o "Settore scientifico-disciplinare".
IRIS contiene inoltre alcuni moduli dedicati alla registrazione dei progetti e dei contratti, e alla reportistica avanzata per le attività di valutazione della ricerca
EnglishThe problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only to the graph labels or both to the graph labels and the query string. We show that deciding if there exists a path in a graph that represents a query string with edit operations to vertex labels is an NP-complete problem and it is fixed-parameter tractable when parameterized by the length of the input string. We show that the variants of approximate string matching we consider are not fixed-parameter tractable, when the parameter is (1) the length of the query string and (2) the number of edit operations. Moreover, we provide inapproximability results for these variants of the of approximate string matching problem.
Dondi, R., Mauri, G., & Zoppis, I. (2021). On the complexity of approximately matching a string to a directed graph. INFORMATION AND COMPUTATION [10.1016/j.ic.2021.104748].
| Citazione: | Dondi, R., Mauri, G., & Zoppis, I. (2021). On the complexity of approximately matching a string to a directed graph. INFORMATION AND COMPUTATION [10.1016/j.ic.2021.104748]. | |
| Tipo: | Articolo in rivista - Articolo scientifico | |
| Carattere della pubblicazione: | Scientifica | |
| Presenza di un coautore afferente ad Istituzioni straniere: | No | |
| Titolo: | On the complexity of approximately matching a string to a directed graph | |
| Autori: | Dondi, R; Mauri, G; Zoppis, I | |
| Autori: | ZOPPIS, ITALO FRANCESCO (Corresponding) | |
| Data di pubblicazione: | 2021 | |
| Lingua: | English | |
| Rivista: | INFORMATION AND COMPUTATION | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.ic.2021.104748 | |
| Appare nelle tipologie: | 01 - Articolo su rivista |
File in questo prodotto:
http://hdl.handle.net/10281/318816
Copyright © 2022