Constructive Packings by Linear Hypergraphs
Constructive Packings by Linear Hypergraphs
复制标题
线性超图的构造性堆积
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
B. Nagle
中科院分区：
文献类型：
--
作者：
Jill Dizona;B. Nagle
对于k-图F0和H， H的F0-packing是H中F0的成对边不相交副本的一个族$mathscr{F}$，设νF0(H)表示H的F0-packing的最大大小|$mathscr{F}$|。在图的情况下，对于大多数固定的F0(Dor和Tarsi[6])，计算νF0(H)是np困难的。本文考虑了F0是一个固定的线性k图的情况。我们建立了一种算法，对于ζ > 0和给定的k-图H，在|V(H)|和F0-packing的H中构造时间多项式，其大小至少为νF0(H)−ζ |V(H)|k。我们的结果扩展了Haxell和Rödl，他们建立了图的类似算法。
For k-graphs F0 and H, an F0-packing of H is a family $mathscr{F}$ of pairwise edge-disjoint copies of F0 in H. Let νF0(H) denote the maximum size |$mathscr{F}$| of an F0-packing of H. Already in the case of graphs, computing νF0(H) is NP-hard for most fixed F0 (Dor and Tarsi [6]). In this paper, we consider the case when F0 is a fixed linear k-graph. We establish an algorithm which, for ζ > 0 and a given k-graph H, constructs in time polynomial in |V(H)| an F0-packing of H of size at least νF0(H) − ζ |V(H)|k. Our result extends one of Haxell and Rödl, who established the analogous algorithm for graphs.