已知拓扑下的4度Steiner树算法

• 作者: 叶继昌 徐寅峰
• 来源期刊: 西安交通大学学报
• 关键词: Steiner树 拓扑 网络
• 年，卷（期）: 1999,（6）
• 页码范围: 90-93
• 页数: 4页
• 分类号: TN711|O157.5
• 语种: 中文
• DOI: 10.3321/j.issn:0253-987X.1999.06.022

摘要

设N为平面上2n个固定点的集合,M为n-2个可动点的集合,E为连接这些点的边的集合(也称作拓扑).设E为点集V上的满4度Steiner拓扑(满Steiner拓扑也就是满足固定点的度为1,可动点的度为4的树的拓扑),H(E)为包含E在内的所有E的退化拓扑的集合.文中构造了计算拓扑属于H(E)的4度Steiner树算法,并证明了算法的时间复杂性是O(n2).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐寅峰		138	1984	23.0	37.0
2	叶继昌		2	9	2.0	2.0