Numerical experimental considerations of optimal spanning tree search problems based on successive applications of elementary transformations

摘要

This paper presented an algorithm for P and NP problems of optimal spanning tree search based on successive applications of elementary transformations, such as minimum spanning tree search-, shortest path tree search- and maximum leaf spanning tree search problem. A proposed algorithm is to find a path from initial vertex to optimum vertex on the tree-graph of given graph, in which the length of the path is related to the computational complexity. Numerical experiments showed us that the algorithm can find the exact solutions for P-problems with same computational complexity as that of established methods. Even for NP problems, experimental results on the problem of maximum leaf spanning tree indicated the usefulness of the algorithm.