Steiner Trees and Related Problems

斯坦纳树及相关问题

• 批准号: 9208913
• 负责人: Ding-Zhu Du
• 金额: $ 11.93万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-03-01 至 1996-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9208913&HistoricalAwards=false
• 关键词: Steiner; Trees; Related; Problems

This research concentrates on the analysis and design of heuristics for Steiner minimum trees and related problems. These improvements are based on extensions of recent research on Steiner ratio and better heuristics for Steiner minimum trees. Various researchers have already discovered new methods of studying Steiner tree problems. With such methods, two long-standing problems were recently solved. The goal is to deepen and extend these methods to solve other open problems and to improve heuristics for Steiner minimum trees and other related problems. The research covers the following two aspects: (1) analysis of heuristics; and (2) construction of heuristics.

这项研究集中于针对斯坦纳最小树和相关问题的启发式方法的分析和设计。 这些改进是基于对Steiner比率的最新研究的扩展以及对Steiner最小树的更好启发式方法。 各种研究人员已经发现了研究Steiner树问题的新方法。 通过这种方法，最近解决了两个长期存在的问题。 目的是加深和扩展这些方法，以解决其他开放问题，并改善施泰纳最小树木和其他相关问题的启发式方法。 该研究涵盖了以下两个方面：（1）启发式分析； （2）启发式法。