文章基本信息

标题：Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
本地全文：下载
作者：Archita Agarwal ; Venkatesan T. Chakaravarthy ; Anamitra Roy Choudhury 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：24
页码：249-261
DOI：10.4230/LIPIcs.FSTTCS.2013.249
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：approximation algorithms; set cover problem; tree cover