The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
The Algorithmic Aspects of Uncrowded Hypergraphs
Claudia Bertram-Kretzberg, Hanno Lefmann,
Pages. 201-230
Abstract We consider the problem of finding deterministically a large
independent set of guaranteed size in a hypergraph on $n$ vertices
and with $m$ edges. With respect to the Turan bound, the quality
of our solutions is better for hypergraphs with not too many small
cycles by a logarithmic factor in the input size. The algorithms
are fast; they often have a running time of $O(m)+o(n^3)$. Indeed,
the denser the hypergraphs are the closer the running times are to
the linear times. For the first time, this gives for some
combinatorial problems algorithmic solutions with state-of-the-art
quality, solutions of which only the existence was known to data.
In some cases, the corresponding upper bounds match the lower
bounds up to constant factors. The involved concepts are uncrowded
hypergraphs.
Contents 1. Introduction 2. Uncrowded hypergraphs 3. Choosing small subhypergraphs 4. Avoiding 2-cycles 5. Applications
Key words independence number, approximation algorithm
Mathmatical Subject Classification 6825, 68R05, 68R10