The 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.
The complexity of minimum difference cover / C. Mereghetti, B.S. Palano. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 4:2(2006), pp. 239-254.
Titolo: | The complexity of minimum difference cover |
Autori: | MEREGHETTI, CARLO (Primo) PALANO, BEATRICE SANTA (Ultimo) |
Parole Chiave: | Difference cover; NP-completeness; NP-hardness |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2006 |
Rivista: | |
Tipologia: | Article (author) |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.jda.2005.03.004 |
Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |