A heuristic algorithm for the mini-max spanning forest problem

Takeo Yamada

doi:10.1016/0377-2217(94)00335-1

A heuristic algorithm for the mini-max spanning forest problem

1996-06-01

17

PRE

AI

DOI：10.1016/0377-2217(94)00335-1

原文链接

原文求助

摘要

En 中文

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.

Keyword:

spanning forest

mini-max problem

heuristics

graph theory

A heuristic algorithm for the mini-max spanning forest problem

摘要

AI总结

期刊

机构

引用论文