论文标题
性能保证的最小连接统治集合的进化算法
Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set
论文作者
论文摘要
连接的主导集是无线传感器网络虚拟主干的广泛采用模型。在本文中，我们为最小连接的主体集合问题（MINCD）设计了一种进化算法，其性能在理论上是根据计算时间和近似比的。给定连接的图$ g =（v，e）$，连接的主导集（CD）是一个子集$ c \ subseteq v $，使得在$ v \ setminus c $中的每个顶点都在$ c $中具有邻居，并且连接了$ c $。 MINCD的目标是找到最低基数的CD $ G $。我们表明，我们的进化算法可以在预期的$ o（n^3）$时间中找到一个CD，该$（n^3）$时间近似于因子$（2+ \lnδ）$内的最佳值，其中$ n $和$ n $和$Δ$分别是顶点和最大图形$ g $。
A connected dominating set is a widely adopted model for the virtual backbone of a wireless sensor network. In this paper, we design an evolutionary algorithm for the minimum connected dominating set problem (MinCDS), whose performance is theoretically guaranteed in terms of both computation time and approximation ratio. Given a connected graph $G=(V,E)$, a connected dominating set (CDS) is a subset $C\subseteq V$ such that every vertex in $V\setminus C$ has a neighbor in $C$, and the subgraph of $G$ induced by $C$ is connected. The goal of MinCDS is to find a CDS of $G$ with the minimum cardinality. We show that our evolutionary algorithm can find a CDS in expected $O(n^3)$ time which approximates the optimal value within factor $(2+\lnΔ)$, where $n$ and $Δ$ are the number of vertices and the maximum degree of graph $G$, respectively.
