Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time chosen the vertex with highest number of edges, or something similar
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ BTW, there is a simple answer to this on StackExchange itself: cs.stackexchange.com/questions/126935/… $\endgroup$– Inuyasha YagamiJan 20 at 20:44
Add a comment
|
$\begingroup$
$\endgroup$
The solution and the analysis is given in Section 6.2.1 and 6.3 of the Book: Probability and Computing Randomized Algorithms and Probabilistic Analysis
Sometimes it is better to refer to a book rather than formulating an answer by ourselves :)
answered Jan 20 at 20:38