Computing coverage kernels under restricted settings

dc.creatorBarbay, Jérémy
dc.creatorPérez-Lantero, Pablo
dc.creatorRojas-Ledesma, Javiel
dc.date.accessioned2019-05-31T15:19:54Z
dc.date.available2019-05-31T15:19:54Z
dc.date.created2019-05-31T15:19:54Z
dc.date.issued2018
dc.identifierLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volumen 10976 LNCS, 2018, Pages 180-191
dc.identifier16113349
dc.identifier03029743
dc.identifier10.1007/978-3-319-94776-1_16
dc.identifierhttps://repositorio.uchile.cl/handle/2250/169393
dc.description.abstractWe 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.
dc.languageen
dc.publisherSpringer Verlag
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
dc.sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectTheoretical Computer Science
dc.subjectComputer Science (all)
dc.titleComputing coverage kernels under restricted settings
dc.typeArtículo de revista


Este ítem pertenece a la siguiente institución