𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A polynomial algorithm for constructing families of k-independent sets

✍ Scribed by G. Freiman; E. Lipkin; L. Levitin

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
1003 KB
Volume
70
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The present paper describes an algorithm for constructing families of k-independent subsets & of {1,2, . . . , n} with &I >2ck", where c, = d/(k -1)2& and d is a certain constant. The algorithm has a polynomial complexity with respect to the size of the family constructed.

πŸ“œ SIMILAR VOLUMES

Explicit construction of exponential siz
Explicit construction of exponential sized families of k-independent sets
✍ N Alon πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 184 KB

Error correcting codes are used to describe explicit collections Fk of subsets of {1, 2,... n}, with IFkl > 2 ckn (ck > 0), such that for any selections A, B of kl and k 2 of members of Fk with kl + k2 = k, there are elements in all the members of A and not in the members of B. This settles a proble

Constructibility of the Set of Polynomia
Constructibility of the Set of Polynomials with a Fixed Bernstein–Sato Polynomial: an Algorithmic Approach
✍ Anton Leykin πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 279 KB

Let n and d be positive integers, let k be a field and let P(n, d; k) be the space of the non-zero polynomials in n variables of degree at most d with coefficients in k. Let B(n, d) be the set of the Bernstein-Sato polynomials of all polynomials in P(n, d; k) as k varies over all fields of character

A construction for large families of k-e
A construction for large families of k-element sets having the ErdΓΆs intersection property
✍ Richard Dean πŸ“‚ Article πŸ“… 1985 πŸ› Elsevier Science 🌐 English βš– 77 KB

## Dedicated to E. Corominas Kleitman, Shearer et Sturtevant ont 6tudi6 le probl~me de trouver l'entier maximum m pour lequel il existe une famille de m ensembles A1,..., Am, tous ~ k 616ments, satisfaisant la propri6t6 d'intersection d'Erd6s: A v f3 Aq Β’ AT d~s que p, q, r sont distincts. Nous do

Algorithms for a maximum clique and a ma
Algorithms for a maximum clique and a maximum independent set of a circle graph
✍ F. Gavril πŸ“‚ Article πŸ“… 1973 πŸ› John Wiley and Sons 🌐 English βš– 523 KB

## Abstract Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum indepen

Analysis of parallel algorithms for find
Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph
✍ H. Chen; A. M. Frieze πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 726 KB

It is well known [9] that finding a maximal independent set in a graph is in class J%, and [lo] that finding a maximal independent set in a hypergraph with fixed dimension is in %JV"%' . It is not known whether this latter problem remains in A% when the dimension is part of the input. We will study