Reduced Order Backtracking Algorithm for Minimum Connected Vertex Covering Problem
The NP-hard problem in combinatorial optimization has a strong practical engineering application back-ground in many fields such as operations research and management science,and has attracted many scholars to study.The research results have remarkable effects in practical applications,but there are still some areas worth improving.For NP-hard problems in combinatorial optimization,although it is relatively simple in mathematical expression,the difficulty with solving will become extremely difficult with the scale of the problem.Using the traditional exact algorithm to solve the problem,although the optimal solution of the problem can be solved,the solving time is generally intolerable for large-scale problems.Heuristic algorithms are often used to solve large-scale NP-hard problems.However,although heuristic algorithms are fast,they can not obtain the optimal solution of the problem in general,and can only obtain a feasible solution with good quality through many large-scale experiments.However,in general,only an approximate solution can be provided,and the exact solution is required by practical engineering.Therefore,it is of great significance to study the mathematical properties and exact algorithms with low time complexity for such problems,which can not only overcome the shortcomings of existing algorithms,but also provide basic mathematical properties and new research ideas for designing other algorithms.Therefore,starting from the algorithm for the minimum connected vertex cover problem,this paper proposes a reduced-order backtracking algorithm based on the mathematical properties of the problem.By desig-ning the exact algorithm based on the mathematical properties of the problem,it can not only overcome the short-coming that the heuristic algorithm can not obtain the optimal solution in general cases,but also improve the shortcomings of the traditional exact algorithm for this problem,which has high worst time complexity.In addition,studying the general mathematical properties of NP-hard problems and applying the mathemati-cal properties of specific problems to the actual algorithm design can not only provide a strong mathematical basis for the design of lower complexity exact algorithms,but also play a positive role in the design of heuristic algorithms and approximation algorithms with lower time complexity.The Minmum Connected Vertex Cover(MCVC)problem is derived from the Minmum Vertex Cover(MVC)problem.The MCVC problem on general graphs is NP-hard.This problem has important application value in the design of wireless network,the arrangement of communication fiber,and the laying of floor electrical lines.To a certain extent,it can not only reduce the resource waste of network line laying and electrical line laying,but also reduce the waste of power resources,and play a role in reducing power loss and improving the utilization efficiency of power resources.The MCVC problem was first proposed by M.R.Garey and D.S.Johnson when they studied the NP-hard problem of rectilinear Steiner tree,which is to find a connected vertex cover set with the minimum number of vertices in a given undirected graph.Firstly,this paper studies the mathematical properties of the problem.Some of the mathematical properties can determine whether some vertices are in or not in the minimum connected vertex covering set in batches,so as to reduce the scale of the problem and improve the speed of the accurate algorithm.Secondly,on the basis of mathematical properties,the upper and lower bound sub algorithm,reduced order sub algorithm and backtrack-ing sub algorithm are designed to solve the optimal solution of the problem.Finally,time complexity analysis and examples of wireless network design show that the algorithm can not only obtain the optimal solution of the problem,but also has lower time complexity than the general accurate algorithm.
minimum connected vertex coverupper bound sub algorithmlower bound sub algorithmbacktracking sub algorithm
国家科技期刊平台
NSTL
万方数据
维普
