Fast Algorithms for MIN INDEPENDENT DOMINATING SET

机译：最小独立域集的快速算法

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We first devise a branching algorithm that computes a minimum independent dominating set with running time O~*(2~(0.424n)) and polynomial space. This improves the O~*(2~(0.441n)) result by (S. Gaspers and M. Liedloff, A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, Proc. WG'06). We then study approximation of the problem by moderately exponential algorithms and show that it can be approximated within ratio 1 + ∈, for any ∈ > 0, in a time smaller than the one of exact computation and exponentially decreasing with ∈. We also propose approximation algorithms with better running times for ratios greater than 3.

机译：我们首先设计一种分支算法，该算法计算运行时间为O〜*（2〜（0.424n））和多项式空间的最小独立控制集。（S. Gaspers and M. Liedloff，一种用于在图中找到最小独立支配集的分支-减少算法，Proc。WG'06）改进了O〜*（2〜（0.441n））结果。然后，我们通过中等指数算法研究问题的逼近，并表明对于任意ε> 0，它都可以在比率1 +ε内近似，并且比精确计算的时间更短，并且随着ε呈指数减小。对于比率大于3的情况，我们还提出了运行时间更好的近似算法。

著录项

来源
《Structural information and communication complexity》|2010年|p.247-261|共15页
会议地点 Sirince(TR);Sirince(TR)
作者
Nicolas Bourgeois; Bruno Escoffier; Vangelis Th. Paschos;
展开▼
作者单位

LAMSADE, CNRS and Universite Paris-Dauphine, F-75775 Paris, France;

LAMSADE, CNRS and Universite Paris-Dauphine, F-75775 Paris, France;

LAMSADE, CNRS and Universite Paris-Dauphine, F-75775 Paris, France;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类信息处理（信息加工）;通信网;
关键词

相似文献

外文文献
中文文献
专利

1. Fast algorithms for min independent dominating set [J] . Bourgeois N., Della Croce F., Escoffier B., Discrete Applied Mathematics . 2013,第4a5期

机译：最小独立支配集的快速算法
2. Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets [J] . Gaspers Serge, Sorkin Gregory B. ACM transactions on algorithms . 2017,第4期

机译：单独，测量和征服：最大2-CSP的多项式空间算法和数量计数的主导集合
3. Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms [J] . Bourgeois N., Escoffier B., Paschos V.T. Discrete Applied Mathematics . 2011,第17期

机译：用中等指数算法逼近最大独立集，最小顶点覆盖及相关问题
4. Fast Algorithms for MIN INDEPENDENT DOMINATING SET [C] . Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos International Colloquium on Structural Information and Communication Complexity . 2010

机译：最小独立主导集的快速算法
5. Independent sets in powers of odd cycles and the global Min-Cut problem. [D] . Natarajan, Venkatesh. 2007

机译：奇数周期和全局最小割问题的幂的独立集。
6. Minimum Connected Dominating Set Algorithms for Ad Hoc Sensor Networks [O] . Xuemei Sun, Yongxin Yang, Maode Ma 2019

机译：Ad Hoc传感器网络的最小连通支配集算法
7. Fast algorithms for min independent dominating set [O] . Bourgeois, N., Della Croce, F., Escoffier, B., 2013

机译：最小独立支配集的快速算法
8. Fault Tree Analysis:Min Cut Set Algorithms. [R] . chatterjee, purnendu 1974

机译：故障树分析：最小割集算法。

Fast Algorithms for MIN INDEPENDENT DOMINATING SET

摘要

著录项

相似文献

相关主题

期刊订阅