Effective heuristics on graph optimization problems

Abstract

Minimum vertex cover, Maximum clique and Minimum connected dominating set problems are well known Graph Optimization problems. These problems are shown to be NP-complete by Karp. As fundamental graph theoretic problem, all these problems occurs in variety of real world applications, including wireless telecommunications, civil, electrical engineering, newlinemultiple sequence alignments in computational biochemistry, to name a few. newlineIn classical complexity these closely related problems are considered equivalent interms of computational difficulty. The variable depth search based local search algorithms are known to be highly effective for several combinatorial and graph optimization problems. The research for this thesis will focus on improvements to the state-of-the-art for solving the minimum vertex cover problem and its associated decision problems. We have developed newlinetwo edge based local search algorithms for the optimization version of minimum weighted/unweighted vertex cover problems. A parameter support of vertices defined in the proposed approaches. The proposed heuristics tested on a wide range of test problems from various sources, includes thousands of random graphs. We investigate the solution obtained by proposed approaches by comparing it, with the other recent heuristic and meta-heuristic developed for these problems. The introduced parameter support of vertices, newlinegreatly reduce more number of random selections among vertices and the newlinenumber of iterations and also the running times to get a near optimal solution. To benchmark the proposed approaches, they were tested with the DIMACS and BHOSLIB benchmark instances of maximum clique problem. newlineThe obtained results show that the proposed approaches outperformed recently developed heuristics in both solution quality and running time of the problem concerned and also indicate that proposed approaches are capable of achieving state-of-the-art performance for the maximum clique problem newlinewith reasonable running times. We explore the applicability of