一类扩展的Steiner树优化问题及其应用

摘要

本文提出了一个计算机网络通信和分布式系统中的一类扩展的Steiner树问题.对此问题设计了两个求其最优解的算法.这两个算法的时间复杂性分别是O(3k-1·n+2k-1·n2)和O(2n-k·n2).其中,k是一棵Steiner树需支撑的给定顶点的个数.