A Class Of Graph Covering Problem And Its Algorithm Design

Covering is one of basic problem in graph theory,it not only has great theoretical significance but also wide applications in practice,for example,in computer graphics,management science and operations research,etc.There are many types of covering problems in graph theory and combinatorial optimization,for example,set cover,vertex cover,edge cover,path cover,etc.In this thesis,we focus on a special covering--H-equicovering problems.A graph is called H-equicoverable if every minimal H-coverng in it is also its minimum-covering.We will give a structure characterization of which graph to be H-equicovering and propose an efficient algorithm to find a minimal H-covering.The main content of our thesis is as follows.Firstly,we generalize the results of P3-equicoverable graphs to the multigraph case,a completely characterization of P3-equicoverable multigraphs is proposed in chapter three.Then,we consider the P4-covering in chapter four.We characterize all the P4-equicoverable graphs in case the graph contains cycles with length at least 4.Finally we propose two heuristic to find a minimal P3-covering in general graphs,it is the first paper to consider the algorithm design for H-covering.The main contribution of our thesis is to characterize which class of graphs is P3(P4)-equicoverable,and then propose an approximation algorithms to find a minimal P3-covering in general graph.Some results are obtained from the two aspects of the structure of the graph and algorithm.