2026-07-23T07:58:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4377 2024-03-06T10:34:58Z ddc:004 open_access

Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers Agarwal, Archita Chakaravarthy, Venkatesan T. Choudhury, Anamitra Roy Roy, Sambuddha Sabharwal, Yogish approximation algorithms set cover problem tree cover In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property. This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified distributed and parallel algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. These algorithms run in polylogarithmic communication rounds in the distributed setting and are in NC, in the parallel setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Archita Agarwal and Venkatesan T. Chakaravarthy and Anamitra Roy Choudhury and Sambuddha Roy and Yogish Sabharwal 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.249 urn:nbn:de:0030-drops-43775 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.249 eng https://creativecommons.org/licenses/by/3.0/legalcode