Capacitated vertex covering with applications

Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

In this paper we study the capacitated vertex cover problem, a generalization of the well known vertex cover problem. Given a graph G = (V, E) with weights on the vertices, the goal is to cover all the edges by picking a cover of minimum weight from the vertices. When we pick a copy of a vertex, we pay the weight of the vertex and cover upto a pre-specified number of edges incident on this vertex (its capacity). The problem is NP-hard. We give a primal-dual based 2 approximation and study several generalizations, as well as the problem restricted to trees.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages858-865
Number of pages8
ISBN (Electronic)089871513X
StatePublished - Jan 1 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Conference

Conference13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
CountryUnited States
CitySan Francisco
Period1/6/021/8/02

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Capacitated vertex covering with applications'. Together they form a unique fingerprint.

Cite this