Hardness results and approximation algorithms for (weighted) paired-domination in graphs
Hardness results and approximation algorithms for (weighted) paired-domination in graphs
复制标题
图中（加权）配对支配的硬度结果和近似算法
DOI：
10.1016/j.tcs.2009.08.004
复制
发表时间：
2009-11
影响因子：
1.1
通讯作者：
Chen, Lei
中科院分区：
文献类型：
--
作者：
Zeng, Zhenbing;Lu, Changhong;Chen, Lei
设G=（V，E）是一个无孤立点的简单图.一个顶点集S V是一个成对控制集，如果V−S中的每个顶点在S中都有一个邻居，并且导出子图G[S]有一个完美匹配。本文研究了图的成对控制的逼近困难性。对于加权配对控制，给出了一般图的近似算法和树的精确动态规划算法。
Let G=(V,E) be a simple graph without isolated vertices. A vertex set S⊆V is a paired-dominating set if every vertex in V−S has a neighbor in S and the induced subgraph G[S] has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given.
登录
查看更多内容
DOI：
10.1007/3540069585_65
发表时间：
1976
期刊：
--
影响因子：
--
作者：
通讯作者：
--
DOI：
10.1007/978-3-642-58412-1
发表时间：
1999
期刊：
--
影响因子：
--
作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
通讯作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
DOI：
10.4171/207-1/5
发表时间：
2020-05
期刊：
Decision Support Systems for Water Supply Systems
影响因子：
--
作者：
B. Geißler;Alexander Martin;A. Morsi;Maximilian Walther;O. Kolb;Jens M. Lang;Lisa Wagner
通讯作者：
B. Geißler;Alexander Martin;A. Morsi;Maximilian Walther;O. Kolb;Jens M. Lang;Lisa Wagner
DOI：
10.1007/978-1-4613-0303-9
发表时间：
1998-10
期刊：
--
影响因子：
--
作者：
D. Du;P. Pardalos
通讯作者：
D. Du;P. Pardalos
DOI：
10.1007/b102533
发表时间：
2013
期刊：
Springer US
影响因子：
--
作者：
通讯作者：
--