A note on ‘Algorithms for connected set cover problem and fault-tolerant connected set cover problem’

A flaw in the greedy approximation algorithm proposed by Zhang et al. (2009) [1] for the minimum connected set cover problem is corrected, and a stronger result on the approximation ratio of the modified greedy algorithm is established. The results are now consistent with the existing results on the connected dominating set problem which is a special case of the minimum connected set cover problem.     

集合覆盖问题的模型与算法

集合覆盖问题在网络设计领域中有着良好的应用背景,但它在算法复杂性上却是NP-困难问题。建立了集合覆盖问题的0-1规划模型,给出了源于贪心思想的近似算法,并从原始-对偶规划的角度进行了证明,基于LINGO软件的传感器网络最优设计案例验证了模型的正确性和算法的有效性。     

基于模拟植物生长算法的求解MCCS问题的研究

为了降低耗能和减少花费,提出了对无线传感网络设计中的最小连通集合划分的方法.采用对网络进行Voronoi划分成近似覆盖集合,对不满足连通的情况采用一种基于模拟植物生长算法生成Steiner最优树的连通算法来实现网络连通的方法.通过对算法的时间复杂度分析及算例实验,验证了该算法不但可获得最优解,同时精度和性能也有提高,明显优于其它方法.     

Parallel and serial heuristics for the minimum set cover problem

We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.Research of both authors was supported by NSF Grant No. MIP-8807540.     

Solving the set cover problem on a supercomputer

Supercomputers, such as CRAY-1, CRAY X-MP, CYBER 205, ETA10, … etc, have been regularly used for solving numerical problems. It is very rare that supercomputers are used to solve combinatorial problems. In this paper, we present an efficient vectorized algorithm to solve the set cover problem, which was proved to be NP-complete, on a supercomputer, ETA10-Q108. This algorithm fully utilizes vector instructions. Experiments are performed both on ETA10-Q108 and VAX/8550 for comparison. It takes VAX/8550 1174.5 seconds to solve a set of problem instances while it takes ETA10-Q108 only 26.6 seconds to solve the same set of problems. For a problem instance involving 7000 elements in a set, it takes 47.74 seconds for the supercomputer to solve it. If VAX/8550 is used, it will need roughly 15 hours. Thus we conclude that it is quite feasible to solve the set cover problem by using supercomputers.     

An algorithm based on ant colony optimization for the minimum connected dominating set problem

Ant colony optimization is a well established metaheuristic from the swarm intelligence field for solving difficult optimization problems. In this work we present an application of ant colony optimization to the minimum connected dominating set problem, which is an NP-hard combinatorial optimization problem. Given an input graph, valid solutions are connected subgraphs of the given input graph. Due to the involved connectivity constraints, out-of-the-box integer linear programming solvers do not perform well for this problem. The developed ant colony optimization algorithm uses reduced variable neighborhood search as a sub-routine. Moreover, it can be applied to the weighted and to the non-weighted problem variants. An extensive experimental evaluation presents the comparison of our algorithm with the respective state-of-the-art techniques from the literature. It is shown that the proposed algorithm outperforms the current state of the art for both problem variants. For comparison purposes we also develop a constraint programming approach based on graph variables. Even though its performance deteriorates with growing instance size, it performs surprisingly well, solving 315 out of 481 considered problem instances to optimality.     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.     

The fault-tolerant extension problem for complete multipartitenetworks

We develop a characterization for m-fault-tolerant extensions, and for optimal m-fault-tolerant extensions, of a complete multipartite graph. Our formulation shows that this problem is equivalent to an interesting combinatorial problem on the partitioning of integers. This characterization leads to a new procedure for constructing an optimal m-fault-tolerant extension of any complete multipartite graph, for any m⩾0. The proposed procedure is mainly useful when the size of the graph is relatively small, because the search time required is exponential. This exponential search, however, is not always necessary. We prove several necessary conditions that help us, in several cases, to identify some optimal m-fault-tolerant extensions without performing any search     

Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets

Using quantum annealing to solve an optimization problem requires minor embedding a logic graph into a known hardware graph. In an effort to reduce the complexity of the minor embedding problem, we introduce the minor set cover (MSC) of a known graph \({\mathcal {G}}\): a subset of graph minors which contain any remaining minor of the graph as a subgraph. Any graph that can be embedded into \({\mathcal {G}}\) will be embeddable into a member of the MSC. Focusing on embedding into the hardware graph of commercially available quantum annealers, we establish the MSC for a particular known virtual hardware, which is a complete bipartite graph. We show that the complete bipartite graph \(K_{N,N}\) has a MSC of N minors, from which \(K_{N+1}\) is identified as the largest clique minor of \(K_{N,N}\). The case of determining the largest clique minor of hardware with faults is briefly discussed but remains an open question.     

Fast Algorithms for max independent set

We first propose a method, called “bottom-up method” that, informally, “propagates” improvement of the worst-case complexity for “sparse” instances to “denser” ones and we show an easy though non-trivial application of it to the min set cover problem. We then tackle max independent set. Here, we propagate improvements of worst-case complexity from graphs of average degree?d to graphs of average degree greater than?d. Indeed, using algorithms for max independent set in graphs of average degree 3, we successively solve max independent set in graphs of average degree 4, 5 and?6. Then, we combine the bottom-up technique with measure and conquer techniques to get improved running times for graphs of maximum degree?5 and?6 but also for general graphs. The computation bounds obtained for max independent set are?O ^?(1.1571 ⁿ ), O ^?(1.1895 ⁿ ) and?O ^?(1.2050 ⁿ ), for graphs of maximum (or more generally average) degree?4, 5 and?6 respectively, and?O ^?(1.2114 ⁿ ) for general graphs. These results improve upon the best known results for these cases for polynomial space algorithms.     

一种高效的最小连通支配集贪心算法

连通支配集（CDS）在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法（GCDS）,依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。     

PTAS for connected vertex cover in unit disk graphs

This paper gives the first polynomial time approximation scheme for the connected vertex cover problem in unit disk graphs.     

Adjacency stable connected operators and set levelings

This paper studies morphological connected operators. Particularly, it focuses on an adjacency constraint, as well as on the so-called set levelings. Some important findings are reported in this work. First, the relationships between the so-called adjacency stable operators and set levelings are investigated, and an equivalence is established. This permits to apply some properties to the related operator class. Second, the implications and limits of a property presented elsewhere that states that certain connected operators can be expressed as a sequential composition of an opening and a closing (and vice-versa) based on markers are treated. Then, a commutative property that involves alternated attribute filters is presented. In addition, other related expressions are discussed.     

A comparison of algorithms for connected set openings and closings

The implementation of morphological connected set operators for image filtering and pattern recognition is discussed. Two earlier algorithms based on priority queues and hierarchical queues, respectively, are compared to a more recent union-find approach. Unlike the earlier algorithms which process regional extrema in the image sequentially, the union-find method allows simultaneous processing of extrema. In the context of area openings, closings, and pattern spectra, the union-find algorithm outperforms the previous methods on almost all natural and synthetic images tested. Finally, extensions to pattern spectra and the more general class of attribute operators are presented for all three algorithms, and memory usages are compared     

A linear kernel for a planar connected dominating set

We provide polynomial time data reduction rules for Connected Dominating Set on planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.     

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

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

有向图连通支配集求解算法

定义了有向图指定源点连通支配集问题。借助参数算法中的技术设计了针对该问题的规约规则,通过规约规则的实施来降低原问题的规模;随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集;最后结合规约规则带来的一些良好特性设计了优化规则,通过优化变换的实施进一步缩减由近似算法求得的连通支配集。不同模型随机图上的模拟实验表明这些规则和算法是有效的。