Matroids and Subset Interconnection Design
Matroids and Subset Interconnection Design
复制标题
拟阵和子集互连设计
DOI：
--
复制
发表时间：
1988
影响因子：
0.8
通讯作者：
Zevi Miller
中科院分区：
文献类型：
--
作者：
D. Du;Zevi Miller
真空系统设计中出现的一个问题，并应用于互连设计的一些自然问题，现描述如下。(1)给定一个集合X和X的子集$X_i，Y_i，i = 1，cdots，n$，满足$X_i cap Y_i = O $，求一个图G，它的顶点集X和最小边数使得对任意i，由$X诱导的子图ackslash Y_i $有一个包含$X_i $的连接组件。与此相关的其他两个问题如下。(2)给定一个集合X及其子集X1，X2，cdots，Xn，使得X = cup _{i = 1}^nX_i $，求一个图G，它的顶点集X和最小边数使得对任意i，由X_i $在G中导出的子图G_i $是连通的. (3)给定一个集合X及其子集X1，X2，cdots，Xn，使得X = cup i = 1 ^nXi，求一个顶点集X的图G，求一个顶点集X的边数最少的图G，使得对于${ 1，cdots，n }$中的任意子集I，由$ cap i in I} Xi $诱导的子图是cup i = 1，cdots，n $.
A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) Given a set X and subsets $X_i ,Y_i $ of $X,i = 1, cdots ,n$, satisfying $X_i cap Y_i = O $, find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by $Xackslash Y_i $ has a connected component containing $X_i $.Two other problems related to this one are the following ones. (2) Given a set X and subsets $X_1 ,X_2 , cdots ,X_n $ such that $X = cup _{i = 1}^n X_i $, find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph $G_i $ induced by $X_i $ in G is connected. (3) Given a set X and subsets $X_1 ,X_2 , cdots ,X_n $ such that $X = cup _{i = 1}^n X_i $, find a graph G with vertex set X, find a graph G with vertex set X and the minimum number of edges such that for any subset I of ${ 1, cdots ,n }$, the subgraph induced by $ cap _{i in I} X_i $ is co...