Maximum Independent Set And Minimum Weak Vertex Cover Problem Solving And Application

Global optimization problems, especially combinatorial optimization problems, are one of the most fundamental problems in scientific research and engineering computation. How to solve such type of problems efficiently have been the core problems of research field of algorithm. Classification of global optimization methods is always divided into deterministic and probabilistic methods. The former has the strictness and integrity in mathematics, but they are difficult to apply in engineering. Typical probabilistic method is difficultly applied to large-scale and complicated global optimization problems. The introduction of heuristics algorithms become a new development phase of deterministic and probabilistic methods and global optimization methods, especially meta-heuristic algorithms.As a new meta-heuristic algorithm, Ant Colony Optimization (ACO) algorithm whose main characteristics are distributed computation, self-organization, positive feedback and constructive greedy heuristic can solve many NP-hard combination optimization problems successfully. As a kind of global search algorithm, ACO algorithm's global optimization capability depends on right selection of parameters to a large extent. A set of unsuitable parameters may result in local optimum of final solution and premature convergence. To compensate some limitations of the basic ACO algorithm, in this paper, we introduce a new hybrid ant colony optimization algorithm: Tabu Search Based Ant Colony Optimization algorithm (TSBACO) that combines ant colony optimization with tabu search strategy to solve Maximum Independent Set (MIS) problem. As compared with ACO algorithm, our proposed TSBACO algorithm showed that global optimization performance and computation efficiency is much better than the ACO algorithm.To enhance the stability and reliability of VLSI (Very Large Scale Integration) systems, fault-tolerant techniques are normally employed in VLSI arrays. Generally, two methods for reconfiguration, namely, the redundancy approach and the degradation approach, are employed in fault-tolerant techniques for VLSI arrays. Both approaches are NP-hard problems. This paper discusses the problem of VLSI arrays reconfiguration based on the redundancy approach. The problem of arrays reconfiguration is translated into the independent set problem of contradiction graph and solving the maximum independent set problem with the TSBACO algorithm and the number of independent set equals to the number of faulty unit. It is proved by experiment to be a simple and useful approach.To further prove the practicability and effectivity of the TSBACO algorithm in combinatorial optimization problems, the TSBACO algorithm is applied to the effective monitor-nodes selection problem in netwok traffic measurement in this paper. We studied minimum vertex cover model of a graph and the problem of seeking monitor-nodes for measuring the network traffic is regarded as the problem of finding out the minimum weak vertex cover which is NP-hard. Then the TSBACO algorithm solving minimum weak vertex cover problem is proposed and the experimental results show that the TSBACO algorithm can find smaller weak vertex cover than other algorithm.