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.

本研究集中于斯坦纳最小树的启发式分析与设计及相关问题。这些改进是基于最近对斯坦纳比的研究的扩展和更好的斯坦纳最小树的启发式。许多研究人员已经发现了研究斯坦纳树问题的新方法。用这种方法，最近解决了两个长期存在的问题。目标是深化和扩展这些方法来解决其他开放问题，并改进斯坦纳最小树和其他相关问题的启发式方法。研究内容包括以下两个方面：(1)启发式分析；(2)启发式的构建。