Loading...
Please wait, while we are loading the content...
Similar Documents
The Algorithmic Aspects of Uncrowded Hypergraphs (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bertram-Kretzberg, Claudia Lefmann, Hanno |
| Description | 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 Tur'an bound, the quality of our solutions is for hypergraphs with not too many small cycles by a logarithmic factor in the input size better. The algorithms are fast; they often have a running time of O(m) + o(n³). Indeed, the denser the hypergraphs are the more close are the running times to the linear ones. This gives for the first time for some combinatorial problems algorithmic solutions with state-of-the-art quality, solutions of which so far only the existence was known. In some cases, the corresponding upper bounds match the lower bounds up to constant factors. The involved concepts are uncrowded hypergraphs. Proc. 8th ACM-SIAM Symposium on Discrete Algorithms SODA |
| File Format | |
| Language | English |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Many Small Cycle Input Size Combinatorial Problem Algorithmic Solution Large Independent Set Involved Concept First Time Guaranteed Size Uncrowded Hypergraphs Logarithmic Factor Running Time Corresponding Upper Bound Algorithmic Aspect State-of-the-art Quality Linear One Constant Factor |
| Content Type | Text |
| Resource Type | Article |
