Integer and fractional packing of families of graphs
Integer and fractional packing of families of graphs
复制标题
图族的整数和分数打包
DOI：
10.1002/rsa.20048
复制
发表时间：
2003
影响因子：
1
通讯作者：
R. Yuster
中科院分区：
文献类型：
--
作者：
R. Yuster
设F是一个图族。对于图G，F-填充数，记为νF（G），是G中F的成对边不相交元素的最大数目。一个从F在G中的元素集到[0，1]的函数σ e是G的一个分数F-填充，如果对每个e ∈ E（G），σe∈H∈F（H）≤ 1。分数F-填充数记为νF*（G），定义为σ H∈（FG）<$（H）在所有分数F-填充<$上的最大值.本文的主要结果是：νF*（G）−νF（G）= o（|V（G）|2）。1、A（A）= A（|V（G）|2）在随机多项式时间内可以找到F在G中的边不交元。对于特殊情况F = {H 0}，我们获得了Haxell和Rödl [Combinatorica 21（2001），13-38]最近的一个困难结果的简单证明，即ν* H 0（G）− ν H 0（G）= o（|V（G）|2）。其结果可以在确定性多项式时间内实现。我们还证明了误差项o（|V（G）|（2）渐近紧。© 2004 Wiley Periodicals，Inc.随机结构算法，2005
Let F be a family of graphs. For a graph G, the F‐packing number, denoted νF(G), is the maximum number of pairwise edge‐disjoint elements of F in G. A function ψ from the set of elements of F in G to [0, 1] is a fractional F‐packing of G if σe∈H∈F ψ(H) ≤ 1 for each e ∈ E(G). The fractional F‐packing number, denoted νF* (G), is defined to be the maximum value of σ H∈( FG) ψ(H) over all fractional F‐packings ψ. Our main result is that νF* (G)−νF(G) = o(|V(G)|2). Furthermore, a set of νF(G)−o(|V(G)|2) edge‐disjoint elements of F in G can be found in randomized polynomial time. For the special case F = {H0} we obtain a simpler proof of a recent difficult result of Haxell and Rödl [Combinatorica 21 (2001), 13–38] that ν* H 0 (G) − ν H 0 (G) = o(|V(G)|2). Their result can be implemented in deterministic polynomial time. We also prove that the error term o(|V(G)|2) is asymptotically tight. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005