Method of conditional probabilities: Difference between revisions

Revision as of 14:34, 18 September 2012

Revision as of 00:06, 25 September 2012

Line 107:

(Say such an edge is ''cut''.)

'''Lemma:<b>''' ''In any graph <math>G=(V,E)</math>, at least <math>|E|/2</math> edges can be cut.'''''

=== Probabilistic proof of Max-Cut lemma ===

Line 295:

* [[Derandomization]]

{{inlineno footnotes|date=June 2012}}

== References ==

* {{Citation

Line 357 ⟶ 358:

<!-- book references generated by http://reftag.appspot.com -->

==External links==

*[http://greedyalgs.info/blog/method-of-conditional-probabilities/ The probabilistic method — method of conditional probabilities], blog entry by Neal E. Young, accessed 19/04/2012.

{{DEFAULTSORT:Method Of Conditional Probabilities}}

[[Category:Algorithms]]