The computation of nearly minimal Steiner trees in graphs
作者:
V. J. Rayward‐Smith†,
期刊:
International Journal of Mathematical Education in Science and Technology
(Taylor Available online 1983)
卷期:
Volume 14,
issue 1
页码: 15-23
ISSN:0020-739X
年代: 1983
DOI:10.1080/0020739830140103
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
The computation of a minimal Steiner tree for a general weighted graph is known to be NP‐hard. Except for very simple cases, it is thus computationally impracticable to use an algorithm which produces an exact solution. This paper describes a heuristic algorithm which runs in polynomial time and produces a near minimal solution. Experimental results show that the algorithm performs satisfactorily in the rectilinear case. The paper provides an interesting case study of NP‐hard problems and of the important technique of heuristic evaluation.
点击下载:
PDF (418KB)
返 回