The minimum global height spanning tree and related problems

Two optimization problems are concerned in this paper, i.e. the minimum global height spanning tree problem and the minimum average height spanning tree problem. Using the time complexity status of 3SAT problem, the two problems are proven to be NP-hard and two algorithms are to be designed for the problems. In nonnegative networks, the time complexities of the two algorithms are all O(n³). Using the complexity status of the first problem, we prove that the minimum height spanning tree problem is NP-hard, so the paper revises an error result given by one of the references.