Constructive Packings of Triple Systems
Constructive Packings of Triple Systems
复制标题
三重系统的建设性填料
DOI：
10.1137/140965107
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
Nagle, Brendan
中科院分区：
文献类型：
--
作者：
Nagle, Brendan
设and为一对图（当k=2时分别写为and）。 of 的打包是 in 的成对边不相交副本族。让表示包装的最大尺寸。 在图 (k=2) 的情况下，Dor 和 Tarsi 证明了对于每个具有三个或更多边的组件的固定图，计算是 NP 困难的。另一方面，Rödl 等人。 （主要参见 [V. Rödl et al. (2007), J. Combin. Theory Ser. B, 97, pp. 245--268]）证明，对于任何固定图，参数可以在时间多项式的误差内近似。特别是 Haxell 和 Rödl [P. Haxell 和 V. Rödl (2001),Combinatorica, 21, pp. 13--38] 对于图 () 构造，对于每个固定图和每个给定图，时间多项式中的尺寸包装。在本文中，我们将 Haxell 和 Rödl 的结果扩展到 k=3。 特别是，对于固定的 3 图，我们建立了一种算法，对于每个给定的 3 图，构造时间多项式中大小的打包。我们的方法基于 Haxell 和 Rödl 的方法，并使用他们和作者早期论文中的超图正则工具，以及此处证明的一些细节。
Letandbe a pair of-graphs (writtenand, respectively, when k=2). An-packing ofis a familyof pairwise edge-disjoint copies ofin. Letdenote the maximum sizeof an-packingof. Already in the case of graphs (k=2), Dor and Tarsi proved that computingis NP-hard for every fixed graphhaving a component with three or more edges. On the other hand, Rödl et al. (see primarily [V. Rödl et al. (2007),J. Combin. Theory Ser. B, 97, pp. 245--268]) proved that, for any fixed-graph, the parametercan be approximated within an error ofin time polynomial in. In particular, a foundational result of Haxell and Rödl [P. Haxell and V. Rödl (2001),Combinatorica, 21, pp. 13--38] for graphs () constructs, for every fixed graphand for every given graph, an-packingof sizein time polynomial in. In this paper, we extend the result of Haxell and Rödl to k=3. In particular, for a fixed 3-graph, we establish an algorithm which, for alland for every given 3-graph, constructs an-packingofof sizein time polynomial in. Our approach is based on that of Haxell and Rödl, and uses hypergraph regularity tools of them and the author from earlier papers, together with some details proven here.
登录
查看更多内容
超图规律性和准随机性
DOI：
10.1137/1.9781611973068.26
发表时间：
2009
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
B. Nagle;A. Poerschke;V. Rödl;M. Schacht
通讯作者：
M. Schacht
稠密 3 均匀超图中的整数和分数堆积
DOI：
--
发表时间：
2003
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
P. Haxell;B. Nagle;V. Rödl
通讯作者：
V. Rödl
影响因子：
1
作者：
R. Yuster
通讯作者：
R. Yuster
线性超图的构造性堆积
DOI：
--
发表时间：
2013
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
Jill Dizona;B. Nagle
通讯作者：
B. Nagle
设定系统的极端问题
影响因子：
1
作者：
P. Frankl;V. Rödl
通讯作者：
V. Rödl