Transversals of Vertex Partitions in Graphs
Transversals of Vertex Partitions in Graphs
复制标题
图中顶点分区的横截面
DOI：
10.1137/0403018
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
M. Fellows
中科院分区：
文献类型：
--
作者：
M. Fellows
本文研究了如下形式的图的性质：对于顶点集的每一个满足每个划分类中元素个数的上界(或下界)的划分，都有一个横截的划分是独立的(或支配的)集。讨论了它在容错数据存储中的可能应用，给出了作为最小和最大次数函数的参数的界。文中还讨论了相关决策问题的复杂性。
This paper studies graph properties of the following forms: For every partition of the vertex set that satisfies an upper (or lower) bound on the number of elements in each partition class, there is a transversal of the partition that is an independent (or dominating) set. A possible application to fault-tolerant data storage is discussed, and bounds for the parameters that are functions of minimum and maximum degree are established. The complexity of associated decision problems is also addressed.