|
Abstract : |
Abstract. Given the success of recent greedy schemes with tie-breaking rules proposed by the authors, this paper extends the investigation by considering different greedy approaches for the graph bi-partitioning problem. In particular, a new method is proposed (Diff-Greedy) that ameliorates in a significant way the performance of the previously proposed Min-Max-Greedy, while requiring less computation. The computational complexity is demonstrated to be O(jEj), E being the edge set of the graph. Experimental results are presented for a large sample of two classes of randomly generated graphs, one with a connection probability independent of the vertices, the second one with a two-dimensional geometric structure. Remarkably enough, the cut sizes obtained through independent repetitions are close to, and in some cases better than the cut sizes obtainedby more sophisticated techniques based on standard greedy construction followed by local search with prohibition-based diversification (Tabu Search), for comparable running times., |
