IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishThe complexity of searching minimum difference covers, both in (Formula Not Shown) and in (Formula Not Shown), is studied. We prove that these two optimization problems are NP-hard. To obtain this result, we characterize those sets—called extrema—having themselves plus zero as minimum difference cover. Such a combinatorial characterization enables us to show that testing whether sets are not extrema, both in Formula Not Shown and in Formula Not Shown, is NP-complete. However, for these two decision problems we exhibit pseudo-polynomial time algorithms.
http://hdl.handle.net/2434/26955| Titolo: | The complexity of minimum difference cover |
| Autori interni: | PALANO, BEATRICE SANTA (Ultimo) MEREGHETTI, CARLO (Primo) |
| Parole Chiave: | Difference cover; NP-completeness; NP-hardness |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2006 |
| Tipologia: | Article (author) |
| Digital Object Identifier (DOI): | 10.1016/j.jda.2005.03.004 |
| Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
| File | Descrizione | Dimensione | Formato | Tipologia | Licenza | |
|---|---|---|---|---|---|---|
| pubblicato.pdf | 187.38 kB | Adobe PDF | Publisher's version/PDF | Administrator Richiedi una copia |
Copyright © 2017