| Article ID: | iaor1999325 |
| Country: | Netherlands |
| Volume: | 91 |
| Issue: | 3 |
| Start Page Number: | 565 |
| End Page Number: | 572 |
| Publication Date: | Jun 1996 |
| Journal: | European Journal of Operational Research |
| Authors: | Kataoka Seiji, Yamada Takeo, Takahashi Hideo |
| Keywords: | minimum spanning tree |
In this paper we formulate the mini-max spanning forest problem for undirected graphs as a generalization of the minimum spanning tree problem. We prove that the former problem is NP-hard. Then we develop a heuristic algorithm to solve this problem approximately, and give an upper bound for relative errors. Through a series of numerical tests, we examine the performance of the developed algorithm.