k度Steiner最小权网络的线性时间算法

摘要

已知平面上 n个固定点集合 N和 m个可动点集合 M，求互连点集 N∪ M的最短连通网络，要求这个连通网络满足： 　　(1)固定点的度为 1，可动点的度为 k ( k 3)； 　　(2) n = 2＋ (k－ 2) m. 　　网络中每条边的权与可动点的位置有关，问题是如何确定这 m个可动点的位置，使这个连通网络的权最小，这个问题称为 k度 Steiner最小权网络问题 .本文给出了 k为偶数，边权取为 L1距离时计算最小权网络的 O(n ln k)时间算法 .