Capacitated domination: Constant factor approximations for planar graphs

Mong Jen Kao*, D. T. Lee

*此作品的通信作者

研究成果: Conference contribution同行評審

3 引文 斯高帕斯(Scopus)

摘要

We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this problem, we are given a graph with three parameters defined on the vertex set, which are cost, capacity, and demand. The objective of this problem is to compute a demand assignment of least cost, such that the demand of each vertex is fully-assigned to some of its closed neighbours without exceeding the amount of capacity they provide. In this paper, we provide the first constant factor approximation for this problem on planar graphs, based on a new perspective on the hierarchical structure of outer-planar graphs. We believe that this new perspective and technique can be applied to other capacitated covering problems to help tackle vertices of large degrees.

原文English
主出版物標題Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
頁面494-503
頁數10
DOIs
出版狀態Published - 2011
事件22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan
持續時間: 5 12月 20118 12月 2011

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
7074 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference22nd International Symposium on Algorithms and Computation, ISAAC 2011
國家/地區Japan
城市Yokohama
期間5/12/118/12/11

指紋

深入研究「Capacitated domination: Constant factor approximations for planar graphs」主題。共同形成了獨特的指紋。

引用此