Research On The Algorithms Of Graph Search End Vertex Problems On Cographs

A graph search algorithm is the process of systematically visiting all vertices in a graph through edges in the graph.Researchers designed six search algorithms based on different search strategies,including depth-first search,breadth-first search,maximal neighborhood search,lexicographic depth-first search,lexicographical breadth-first search and maximum cardinality search.A graph search algorithm can start from any vertex in a given graph,but which vertices can be the last visited vertex of the search algorithm,this problem has attracted people’s attention in the past ten years,which is graph search end vertex problem.The end vertex problems of these six graph search algorithms are all proved to be NP-complete.This thesis studies the algorithms and complexity of graph search end vertex problems on cographs,and the main contributions are as follows.First,this thesis proves that the depth-first search and breadth-first search end vertex problems are solvable in linear time on cographs.For the depth-first search end vertex problem on cographs,this thesis studies the relationship between it and the minimum path cover problem,and combines the minimum path cover numbers of cographs to propose a characterization for the depth-first search end vertex problem on cographs.This thesis designs a more efficient linear time algorithm for calculating the minimum path cover numbers of cographs,and combines this algorithm to design an algorithm that can solve the depth-first search end vertex problem on cographs in linear time.For the breadth-first search end vertex problem,this thesis proves that any non-universal vertex of a cograph can become the breadth-first search end vertex,and for the universal vertices,this thesis proposes a characterization for this problem on general graphs.Combining these two points further proves that this problem has a linear time solution algorithm on cographs.Second,this thesis also presents linear time solutions for the maximal neighborhood search,lexicographic breadth-first search,and maximum cardinality search end vertex problems on cographs.For the maximal neighborhood search and lexicographic breadth-first search end vertex problems,this thesis proves that they have the same characterization on cographs,that is,they satisfy a specific structure in the cograph’s tree representation(Cotree).This thesis also finds that the structure can be verified by two scans using lexicographic breadth-first search and its variant,and presents two linear time decision algorithms based on cotree and lexicographical breadth-first search,respectively.For the maximum cardinality search end vertex problem,this thesis designs a bottom-up algorithm based on cotree by using the multi-module properties of cograph,and proves that the time complexity of the algorithm is linear.The thesis includes 4 figures,1 table,and 91 references.