부산대학교 도서관

In this paper the authors examine methods for improving the empirical computation time of graph optimization problems asking for spanning trees with some objective on the degrees of the vertices in the tree. Three problems are examined: the Minimum Leaves Problem, the Minimum Branch Vertices Problem, and the Minimum Degree Sum Problem, which are known to be NP-hard. \par The idea behind the improvement methods is that articulation vertices (cut-vertices) in graphs are of special interest in the above three problems, and the difficult portion of solving the problems lies in optimizing the strongly connected (bi-connected) components of a graph. Except for the Minimum Leaves Problem, it is not trivial to just decompose a graph into its strongly connected components and solve them independently of each other, and the main contribution of the paper is to propose how the individual solutions can be combined to get a globally optimal solution. The decomposition of a graph into its strongly connected components can be easily done in linear time as a function of the number of edges in the graph, but there is no known efficient algorithm to solve the sub-problems for each strongly connected component. \par The authors give results of conducted experiments on benchmark instances available in the literature, as well as instances generated by themselves. After decomposing an input graph into its strongly connected components, the authors solve the sub-problems arising from each of the strongly connected components by a commercial integer linear programming (ILP) solver---CPLEX v11.0, using known ILP formulations from the literature.