𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the problem of approximating the number of bases of a matriod

✍ Scribed by Y. Azar; A.Z. Broder; A.M. Frieze

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
237 KB
Volume
50
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximating the Number of Zeroes of a
Approximating the Number of Zeroes of a GF[2] Polynomial
✍ M. Karpinski; M. Luby πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 325 KB

We develop a probabilistic polynomial time algorithm which on input a polynomial \(g\left(x_{1}, \ldots, x_{n}\right)\) over \(G F[2], \epsilon\) and \(\delta\), outputs an approximation to the number of zeroes of \(g\) with relative error at most \(\epsilon\) with probability at least \(1-\delta\).

On Hadwiger's numberβ€” a problem of the N
On Hadwiger's numberβ€” a problem of the Nordhaus-Gaddum type
✍ M. Stiebitz πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 700 KB

Stiebitz, M., On Hadwiger's number-A problem of the Nordhaus-Gaddum type, Discrete Mathematics 101 (1992) 307-317. The Hadwiger number of a graph G = (V, E), denoted by q(G), is the maximum size of a complete graph to which G can be contracted. Let %((n, k):= {G 1 IV(G)1 = n and n(G) = k}. We shall