3
$\begingroup$

David Karger developed an algorithm for estimating graph reliability; a key lemma in this algorithm is that if a graph has minimal cut-set size $c$, then the number of cut-sets of size $\alpha c$ is $\leq n^{2 \alpha}$.

However, these cuts need not be minimal (a cut-set is minimal iff it contains no smaller cut-set). Are there any better bounds on the number of minimal cut-sets of size $\leq \alpha c?$

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.