网络的分区连接问题  

The Piecewise Connection Problem in Networks

作　　者：吕红杰[1] 杨爱峰[1] 

机构地区：[1]郑州大学数学系,河南郑州450052

出　　处：《运筹与管理》2003年第1期28-32,共5页Operations Research and Management Science

摘　　要：本文研究了最小支撑树问题的一个变形———分区连接问题 ,即对给定的赋权图及其中若干个顶点 ,求赋权图的权最小支撑森林 ,使得它的每一个分支恰包含唯一的指定顶点。本文给出了该问题的一个时间复杂性为O(|V|2 )的算法。此外 ,还研究了与该问题相关的另外三个问题。In this paper, we study a generalization of the minmum spanning tree problem, the piecewise connection problem. Given a weighted graph and some vertices,we find a minimum spanning forest in which each component contains just one given vertex. An algorithm with the time complexity O(｜V｜ 2)is given. Moreover, this paper studies some related problems.

关 键 词：网络优化 分区连接 多项式算法 NP-完全性 

分 类 号：O233[理学—运筹学与控制论]