Abstract Dominating set is a set of vertices of a graph such that all other vertices have a neighbour in the dominating set. We propose a new order-based randomised local search (RLS o ) algorithm to solve minimum dominating set problem in large graphs. Experimental evaluation is presented for multiple types of problem instances. These instances include unit disk graphs, which represent a model of wireless networks, random scale-free networks, as well as samples from two social networks and real-world graphs studied in network science. Our experiments indicate that RLS o performs better than both a classical greedy approximation algorithm and two metaheuristic algorithms based on ant colony optimisation and local search. The order-based algorithm is able to find small dominating sets for graphs with tens of thousands of vertices. In addition, we propose a multi-start variant of RLS o that is suitable for solving the minimum weight dominating set problem. The application of RLS o in graph mining is also briefly demonstrated.
In the application of a similar idea to the minimum weight dominating set problem, a preprocessing phase has been added to a similar algorithm called ACO-PP-LS @cite_3 . This algorithm extended ACO-LS by adding a routine of generating @math maximal independent sets using a greedy algorithm and improving the pheromone values of vertices in these independent sets. These independent sets were constructed by using a list of vertices available for adding to the independent set. In the beginining, a random vertex is added to the independent set. This vertex and its neighbours are then excluded from the list of available vertices. This is process iterated until there are no more vertices available. This preprocessing routine helps the algorithm to start with a probabilistic model that is not entirely random, leading to more rapid convergence for some instances. In ACO-PP-LS, slighly different values of parameters @math and @math have also been used. These were @math and @math . We will use the original parameterisations of ACO-LS @cite_42 and ACO-PP-LS @cite_3 in our further experimental investigations.
@cite_42 @cite_3
2249156935 1964089073 1978232925 43777471
In this paper we present an application of ant colony optimization (ACO) to the Minimum Weighted Dominating Set Problem. We introduce a heuristic for this problem that takes into account the weights of vertexes being covered and show that it is more efficient than the greedy algorithm using the standard heuristic. Further we give implementation details of ACO applied to this problem. We tested our algorithm on graphs with different sizes, edge densities, and weight distribution functions and shown that it gives greatly improved results over these acquired by the greedy algorithms. Abstract A simple parallel randomized algorithm to find a maximal independent set in a graph G = ( V , E ) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O (| E | d max ) processors is O (log n ), where d max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O (| E |) processors the algorithm runs in O (log 2 n ). Previously, an O (log 4 n ) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O (log 2 n ) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d -wise rather than fully independent random choices (for some constant d ) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments. In this paper an ant colony optimization (ACO) algorithm for the minimum connected dominating set problem (MCDSP) is presented. The MCDSP become increasingly important in recent years due to its applicability to the mobile ad hoc networks (MANETs) and sensor grids. We have implemented a one-step ACO algorithm based on a known simple greedy algorithm that has a significant drawback of being easily trapped in local optima. We have shown that by adding a pheromone correction strategy and dedicating special attention to the initial condition of the ACO algorithm this negative effect can be avoided. Using this approach it is possible to achieve good results without using the complex two-step ACO algorithm previously developed. We have tested our method on standard benchmark data and shown that it is competitive to the existing algorithms. [Projekat Ministarstva nauke Republike Srbije, br. III-44006] Minimum dominating set, which is an NP-hard problem, finds many practical uses in diverse domains. A greedy algorithm to compute the minimum dominating set is proven to be the optimal approximate algorithm unless P=NP. Meta-heuristics, generally, find solutions better than simple greedy approximate algorithms as they explore the search space better without incurring the cost of an exponential algorithm. However, there are hardly any studies of application of meta-heuristic techniques for this problem. In some applications it is important to minimize the dominating set as much as possible to reduce cost and or time to perform other operations based on the dominating set. In this paper, we propose a hybrid genetic algorithm and an ant-colony optimization (ACO) algorithm enhanced with local search. We compare the performance of these two hybrid algorithms against the solutions obtained using the greedy heuristic and another hybrid genetic algorithm proposed in literature. We find that the ACO algorithm enhanced with a minimization heuristic performs better than all other algorithms in almost all instances.