On bicriterion minimal spanning trees: An approximation

In this paper we focus on the problem of computing the set of efficient spanning trees for a given network where each arc carries two attributes. This problem is -complete. We discuss two heuristics, namely, neighbourhood search (which is a well-known method) and adjacent search, a new method. They both approximate the set of efficient spanning trees. The difference lies in which kind of spanning trees are generated in each iteration. For neighbourhood search, all spanning trees which are adjacent to at least one spanning tree in the current approximation set are considered. Adjacent search is similar to neighbourhood search except that only spanning trees which are adjacent to at least two spanning trees in the current approximation set are considered. Based on computational results it is concluded that adjacent search is a reasonable alternative to neighbourhood search, especially for large problems.