无向图中连通支配集问题的精确算法

Exact algorithm for connected dominating set in undirected graphs

图G=(V,E)的一个支配集D?V是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G[S]是连通图。该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂度为O*(1. 93n)的精确算法。

A dominating set D V of a graph G=(V,E ) was a subset of vertices, such that every vertex of G was either in D , or adjacent to at least one vertex in D . The connected dominating set problem asks to find a dominating set S with minimum number of vertices and the induced subgraph G[S] of S was connected. The connected dominating set problem was a classical NP-hard problem, which could be applied to connected facility location, Ad-hoc networks and many other areas. For the connected dominating set problem in undirected graphs, this paper carefully analyzed the structural properties, explored a number of effective reduction rules as well as branching rules and provided a branch-and-search algorithm. A measure- and-conquer method is also introduced to analyze the running time bound. Finally, an exact algorithm with a running time complexity of O *(1.93 n) is obtained.