Integer and fractional packings of hypergraphs

V. Rödl; M. Schacht; M. H. Siggers; N. Tokushige

doi:10.1016/j.jctb.2006.05.006

Integer and fractional packings of hypergraphs

V. Rödl
, M. Schacht
, M. H. Siggers
, N. Tokushige

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

Let F₀ be a fixed k-uniform hypergraph. The problem of finding the integer F₀-packing number ν_F0 (H) of a k-uniform hypergraph H is an NP-hard problem. Finding the fractional F₀-packing number ν_F0^* (H) however can be done in polynomial time. In this paper we give a lower bound for the integer F₀-packing number ν_F0 (H) in terms of ν_F0^* (H) and show that ν_F0 (H) ≥ ν_F0^* (H) - o (| V (H) |^k).

Original language	English
Pages (from-to)	245-268
Number of pages	24
Journal	Journal of Combinatorial Theory. Series B
Volume	97
Issue number	2
DOIs	https://doi.org/10.1016/j.jctb.2006.05.006
State	Published - Mar 2007

Keywords

Hypergraph regularity lemma
Packings

Access to Document

10.1016/j.jctb.2006.05.006

Cite this

@article{e2f55ea7a7c34c93be6d0263faf7d423,

title = "Integer and fractional packings of hypergraphs",

abstract = "Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number νF0 (H) of a k-uniform hypergraph H is an NP-hard problem. Finding the fractional F0-packing number νF0* (H) however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number νF0 (H) in terms of νF0* (H) and show that νF0 (H) ≥ νF0* (H) - o (| V (H) |k).",

keywords = "Hypergraph regularity lemma, Packings",

author = "V. R{\"o}dl and M. Schacht and Siggers, \{M. H.\} and N. Tokushige",

year = "2007",

month = mar,

doi = "10.1016/j.jctb.2006.05.006",

language = "English",

volume = "97",

pages = "245--268",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Integer and fractional packings of hypergraphs

AU - Rödl, V.

AU - Schacht, M.

AU - Siggers, M. H.

AU - Tokushige, N.

PY - 2007/3

Y1 - 2007/3

N2 - Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number νF0 (H) of a k-uniform hypergraph H is an NP-hard problem. Finding the fractional F0-packing number νF0* (H) however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number νF0 (H) in terms of νF0* (H) and show that νF0 (H) ≥ νF0* (H) - o (| V (H) |k).

AB - Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number νF0 (H) of a k-uniform hypergraph H is an NP-hard problem. Finding the fractional F0-packing number νF0* (H) however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number νF0 (H) in terms of νF0* (H) and show that νF0 (H) ≥ νF0* (H) - o (| V (H) |k).

KW - Hypergraph regularity lemma

KW - Packings

UR - https://www.scopus.com/pages/publications/33846138016

U2 - 10.1016/j.jctb.2006.05.006

DO - 10.1016/j.jctb.2006.05.006

M3 - Article

AN - SCOPUS:33846138016

SN - 0095-8956

VL - 97

SP - 245

EP - 268

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

Integer and fractional packings of hypergraphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this