Computing coverage kernels under restricted settings
| Author | dc.contributor.author | Barbay, Jérémy | |
| Author | dc.contributor.author | Pérez-Lantero, Pablo | |
| Author | dc.contributor.author | Rojas-Ledesma, Javiel | |
| Admission date | dc.date.accessioned | 2019-05-31T15:19:54Z | |
| Available date | dc.date.available | 2019-05-31T15:19:54Z | |
| Publication date | dc.date.issued | 2018 | |
| Cita de ítem | dc.identifier.citation | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volumen 10976 LNCS, 2018, Pages 180-191 | |
| Identifier | dc.identifier.issn | 16113349 | |
| Identifier | dc.identifier.issn | 03029743 | |
| Identifier | dc.identifier.other | 10.1007/978-3-319-94776-1_16 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/169393 | |
| Abstract | dc.description.abstract | We consider the Minimum Coverage Kernel problem: given a set B of d-dimensional boxes, find a subset of B of minimum size covering the same region as B. This problem is NP -hard, but as for many NP -hard problems on graphs, the problem becomes solvable in polynomial time under restrictions on the graph induced by B. We consider various classes of graphs, show that Minimum Coverage Kernel remains NP -hard even for severely restricted instances, and provide two polynomial time approximation algorithms for this problem. | |
| Lenguage | dc.language.iso | en | |
| Publisher | dc.publisher | Springer Verlag | |
| Type of license | dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | |
| Link to License | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | |
| Source | dc.source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
| Keywords | dc.subject | Theoretical Computer Science | |
| Keywords | dc.subject | Computer Science (all) | |
| Título | dc.title | Computing coverage kernels under restricted settings | |
| Document type | dc.type | Artículo de revista | |
| Cataloguer | uchile.catalogador | jmm | |
| Indexation | uchile.index | Artículo de publicación SCOPUS | |
| uchile.cosecha | uchile.cosecha | SI |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile