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
EnglishIn this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence (ELCS) of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the ELCS of two sequences is NP-hard. On the positive side, we first present an efficient algorithm for the ELCS problem over instances of two sequences where each mandatory symbol can appear in total at most three times in the sequences. Furthermore, we present two fixed-parameter algorithms for the ELCS problem over instances of two sequences where the parameter is the number of mandatory symbols.
Bonizzoni, P., Della Vedova, G., Dondi, R., Fertin, G., Rizzi, R., & Vialette, S. (2007). Exemplar longest common subsequence. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 4(4), 535-543.
| Citazione: | Bonizzoni, P., Della Vedova, G., Dondi, R., Fertin, G., Rizzi, R., & Vialette, S. (2007). Exemplar longest common subsequence. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 4(4), 535-543. | |
| Tipo: | Articolo in rivista - Articolo scientifico | |
| Carattere della pubblicazione: | Scientifica | |
| Presenza di un coautore afferente ad Istituzioni straniere: | Si | |
| Titolo: | Exemplar longest common subsequence | |
| Autori: | Bonizzoni, P; Della Vedova, G; Dondi, R; Fertin, G; Rizzi, R; Vialette, S | |
| Autori: | ||
| Data di pubblicazione: | 2007 | |
| Lingua: | English | |
| Rivista: | IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1109/TCBB.2007.1066 | |
| Appare nelle tipologie: | 01 - Articolo su rivista |
File in questo prodotto:
Copyright © 2021