Approximation algorithms for the capacitated domination problem

Mong Jen Kao*, Han Lin Chen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

We consider the Capacitated Domination problem, which models a service-requirement assignment scenario and is a generalization to the well-known Dominating Set problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service. In terms of polynomial time approximations, we present logarithmic approximation algorithms with respect to different demand assignment models on general graphs. On the other hand, from the perspective of parameterization, we prove that this problem is W[1]-hard when parameterized by a structure of the graph called treewidth. Based on this hardness result, we present exact fixed-parameter tractable algorithms with respect to treewidth and maximum capacity of the vertices. This algorithm is further extended to obtain pseudo-polynomial time approximation schemes for planar graphs.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 4th International Workshop, FAW 2010, Proceedings
Pages185-196
Number of pages12
DOIs
StatePublished - 2010
Event4th International Frontiers of Algorithmics Workshop, FAW 2010 - Wuhan, China
Duration: 11 Aug 201013 Aug 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6213 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Frontiers of Algorithmics Workshop, FAW 2010
Country/TerritoryChina
CityWuhan
Period11/08/1013/08/10

Fingerprint

Dive into the research topics of 'Approximation algorithms for the capacitated domination problem'. Together they form a unique fingerprint.

Cite this