ON THE MINIMUM FEASIBLE GRAPH FOR FOUR SETS
ON THE MINIMUM FEASIBLE GRAPH FOR FOUR SETS
复制标题
关于四组的最小可行图
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Fuxiaobing
中科院分区：
文献类型：
--
作者：
Xuyinfeng;Fuxiaobing
给定一个顶点集X和子集X1，X2，.的完全图，Xn，寻找一个具有最少边数的子图G，使得对于每个i= 1，2，.，n，G在Xi上有一棵生成树，这是在真空系统设计中出现的.在一般情况下，这个问题是NP-完全的，它被证明为n=2和3，这个问题是多项式时间可解的。本文证明了当n=4时，该问题也是多项式时间可解的，并给出了相应图的构造方法。
Given a complete graph with vertex set X and subsets X1,X2,...,Xn, the problem of finding a subgraph G with minimum number of edges such that for every i= 1, 2, ...,n, G contains a spanning tree on Xi, arises in the design of vaccum systems. In general, this problem is NP-complete and it is proved that for n=2 and 3 this problem is polynomial-time solvable. In this paper, we prove that for n=4, the problem is also polynomial-tlme solvable and give a method to construct the corresponding graph.