Cover-Decomposition and Polychromatic Numbers
Cover-Decomposition and Polychromatic Numbers
复制标题
DOI：
10.1007/978-3-642-23719-5_67
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
B. Bollobás;David Pritchard;T. Rothvoss;A. Scott
中科院分区：
文献类型：
--
作者：
B. Bollobás;David Pritchard;T. Rothvoss;A. Scott
如果每个超边至少包含每种颜色的一个顶点，则超图顶点的着色是多色的；多色数是这种着色中颜色的最大数量。它的对偶数，即覆盖分解数，是不相交超边缘覆盖的最大数量。在几何超图中，人们对这些数字的平凡上限（最小超边尺寸和度）进行了下限研究；我们的目标是将研究范围扩大到几何设置之外。我们获得了为三个超图族产生近紧边界的算法：有界超边大小、树中的路径和有界 Vapnik-Chervonenkis (VC) 维。这表明差异理论和迭代线性规划松弛对于覆盖分解是有用的。最后，我们讨论覆盖分解对传感器覆盖的推广。
A coloring of a hypergraph's vertices ispolychromaticif every hyperedge contains at least one vertex of each color; thepolychromatic numberis the maximum number of colors in such a coloring. Its dual, thecover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric hypergraphs, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree); our goal here is to broaden the study beyond geometric settings. We obtain algorithms yielding near-tight bounds for three families of hypergraphs: bounded hyperedge size, paths in trees, and bounded Vapnik--Chervonenkis (VC)-dimension. This reveals that discrepancy theory and iterated linear program relaxation are useful for cover-decomposition. Finally, we discuss the generalization of cover-decomposition to sensor cover.