A Practical Approach for Finding Small {Independent, Distance} Dominating Sets in Large-Scale Graphs
A Practical Approach for Finding Small {Independent, Distance} Dominating Sets in Large-Scale Graphs
复制标题
在大规模图中查找小{独立，距离}支配集的实用方法
DOI：
10.1007/978-3-319-03889-6_18
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Dorothea Wagner
中科院分区：
文献类型：
--
作者：
Liang Zhao;Hiroshi Kadowaki;Dorothea Wagner
假设在一个网络中，一个节点可以支配（或覆盖、监视等）它的邻居节点。一个有趣的问题是找到这样一个最小节点集，它支配所有其他节点。这被称为最小支配集问题。一个自然泛化假设一个节点可以支配距离≥1的节点，称为最小距离支配集问题。另一方面，如果控制集中任意两个节点之间的距离必须至少≥1，则该问题称为最小独立控制集问题。本文考虑寻找任意randz的最小距离独立支配集，它在设施定位、网络监控等方面具有广泛的应用。我们展示了一种实用的方法。实证研究表明，它通常是非常快速和相当准确的，因此适合大数据分析。对有向图的推广，边长度，多重支配也进行了讨论。
Suppose that in a network, a node can dominate (or cover, monitor, etc) its neighbor nodes. An interesting question asks to find such a minimum set of nodes that dominate all the other nodes. This is known as theminimum dominating setproblem. A natural generalization assumes that a node can dominate nodes within a distanceR≥ 1, called the minimumdistancedominating set problem. On the other hand, if the distance between any two nodes in the dominating set must be at leastz≥ 1, then the problem is known as the minimumindependentdominating set problem. This paper considers to find a minimum distance-Rindependence-zdominating set for arbitraryRandz, which has applications in facility location, internet monitoring and others. We show a practical approach. Empirical studies show that usually it is very fast and quite accurate, thus suitable for Big Data analysis. Generalization to directed graphs, edge lengths, multi-dominating are also discussed.