Two algorithms for determining a minimum independent dominating set

The problem of determining a minimum independent dominating set is fundamental to both the theory and applications of graphs. Computationally it belongs to the class of hard combinatorial optimization problems known as NP-hard. In this paper, we develop a backtracking algorithm and a dynamic programming algorithm to determine a minimum independent dominating set. Computational experience with the backtracking algorithm on more than 1000 randomly generated graphs ranging from 100 to 200 vertices and from 10% to 60% densities has shown that the algorithm is effective.     

Approximating minimum coloring and maximum independent set in dotted interval graphs

Dotted interval graphs are introduced by Aumann et al. as a generalization of interval graphs. We study two optimization problems in dotted interval graphs that find application in high-throughput genotyping. We present improved approximations for minimum coloring and the first approximation for maximum independent set in dotted interval graphs.     

A two phase removing algorithm for minimum independent dominating set problem

The minimum independent dominating set (MIDS) problem is a famous combinatorial optimization problem and is widely used in real-world domains. In this paper, we design a novel local search algorithm with tabu method and two phase removing strategies including double-checked removing strategy and random diversity removing strategy to solve the MIDS problem. The first removing strategy checks and then removes the second-level neighbourhood of the just removal vertex to break the limitation of the independence property. When the quality of candidate solution has not been improved after some steps, the second removing strategy dynamically and greedily removes lots of vertices so that the current candidate solution can escape from suboptimal search space, and then we introduce the random walk into the repair process. Experiments are carried out on two classical benchmarks named DIMACS and BHOSLIB, and the results show that the proposed algorithm significantly outperforms the previous state-of-the-art MIDS heuristic algorithms.     

Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks

Motivated by cooperative communication in ad hoc networks, Wu et al. proposed extended dominating set (EDS) where each node in an ad hoc network is covered by either a dominating neighbor or several 2-hop dominating neighbors, and defined two types of dominating sets: extended strongly connected dominating set (ECDS) and extended weakly connected dominating set (EWCDS), according to the success of a broadcast process. An EWCDS is an effective method for clustering. In this paper, we extend the dominative capabilities of nodes such that each forward node dominates not only itself and its regular neighbors fully, but also its quasi-neighbors partly. Based on this extension, three novel algorithms to find EWCDSs in ad hoc networks are proposed. The correctness and performance of our algorithms are confirmed through theoretical analysis and comprehensive simulations.     

Greed is good: Approximating independent sets in sparse and bounded-degree graphs

Theminimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of (Δ+2)/3 for approximating independent sets in graphs with degree bounded by Δ. The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turán’s bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved performance ratio on graphs with average degree , improving on the previous best of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy. Gordon Gekko [29]. A preliminary version of this paper appeared at the 26th ACM Symposium on Theory of Computing, 1994. This work was done while both authors were at the Japan Advanced Institute of Science and Technology, Hokuriku.     

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。     

传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。     

On positive influence dominating sets in social networks

In this paper, we investigate the positive influence dominating set (PIDS) which has applications in social networks. We prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(δ) where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network.     

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +ε)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +ε)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +ε)-approximation algorithm for an MWCDS.     

无线网络中一种简单的弱连通支配集构造策略

通过构造边支配集,提出了求解无线网络中弱连通支配集的集中式构造算法,该算法的时间复杂度为O（|N|+|E|）。同时在保证支配集的支配性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性,并通过仿真验证了算法的有效性。与已有结果相比,该算法可以产生规模更小的弱连通支配集。     

基于最小连通支配集的无线传感器网络容错研究

过多的跳数对于无线传感器网络容错是不利的。无线传感器网络以往的研究中最小连通支配集主要是作为骨干网来使用,通过结合度来构建最小连通支配集,使得所构建的最小连通支配集不仅具备骨干网的功能,还具有容错的作用。提出了构建具有容错作用的基于度的最小连通支配集算法,仿真证明该算法可以有效地减少无线传感器网络的跳数,从而达到增强无线传感器网络容错的目的。     

An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem

The minimum independent dominance set (MIDS) problem is an important version of the dominating set with some other applications. In this work, we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB. The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting. It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps. We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications. The results show that the MAE-PB algorithm achieves high performance. In particular, for the classical benchmarks, the MAE-PB algorithm obtains the best-known results for seven instances, whereas for several massive graphs, it improves the best-known results for 62 instances. We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

Two algorithms for minimum 2-connected r-hop dominating set

For a graph G=(V,E), a subset D⊆V is an r-hop dominating set if every vertex u∈V−D is at most r-hops away from D. It is a 2-connected r-hop dominating set if the subgraph of G induced by D is 2-connected. In this paper, we present two approximation algorithms to compute minimum 2-connected r-hop dominating set. The first one is a greedy algorithm using ear decomposition of 2-connected graphs. This algorithm is applicable to any 2-connected general graph. The second one is a three-phase algorithm which is only applicable to unit disk graphs. For both algorithms, performance ratios are given.     

Approximating minimum cocolorings

A cocoloring of a graph G is a partition of the vertex set of G such that each set of the partition is either a clique or an independent set in G. Some special cases of the minimum cocoloring problem are of particular interest.We provide polynomial-time algorithms to approximate a minimum cocoloring on graphs, partially ordered sets and sequences. In particular, we obtain an efficient algorithm to approximate within a factor of 1.71 a minimum partition of a partially ordered set into chains and antichains, and a minimum partition of a sequence into increasing and decreasing subsequences.     

无线传感器网络中具有容错能力的连通支配集构造算法*

根据无线传感器网络中虚拟骨干节点极易失效的问题,建立了一个具有容错能力的连通支配集。首先提出了一种分布式连通支配集构造算法DACDS;然后在这个算法基础上,根据一般构造容错支配集的规则,提出了容错算法kCDS;最后根据该算法的缺点,对其作了一个改进,并对kCDS和改进kCDS算法进行了仿真。仿真结果表明,改进kCDS算法具有更好的性能。     

Clustering wireless ad hoc networks with weakly connected dominating set

The increasing popular personal communications and mobile computing require a wireless network infrastructure that supports self-configuration and self-management. Efficient clustering protocol for constructing virtual backbone is becoming one of the most important issues in wireless ad hoc networks. The weakly connected dominating set   (WCDS) is very suitable for cluster formation. As finding the minimum WCDS in an arbitrary graph is a NP-Hard problem, we propose an area-based distributed algorithm for WCDS construction in wireless ad hoc networks with time and message complexity O(n)$O(n)$. This Area algorithm is divided into three phases: area partition, WCDS construction for each area and adjustment along the area borders. We confirm the effectiveness of our algorithm through analysis and comprehensive simulation study. The number of nodes in the WCDS constructed by this Area algorithm is up to around 50% less than that constructed by the previous well-known algorithm.     

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.