Artículo de revista
Computing coverage kernels under restricted settings
Fecha
2018Registro en:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volumen 10976 LNCS, 2018, Pages 180-191
16113349
03029743
10.1007/978-3-319-94776-1_16
Autor
Barbay, Jérémy
Pérez-Lantero, Pablo
Rojas-Ledesma, Javiel
Institución
Resumen
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.