Title | ||
---|---|---|
Combining Helpful Sets and Parallel Simulated Annealing for the Graph-partitioning Problem |
Abstract | ||
---|---|---|
In this paper we present a new algorithm for the k-partitioning problem which achievesan improved solution quality compared to known heuristics. We apply the principle of socalled "helpful sets", which has shown to be very efficient for graph bisection, to the directk-partitioning problem. The principle is extended in several ways. We introduce a newabstraction technique which shrinks the graph during runtime in a dynamic way leadingto shorter computation times and improved solutions... |
Year | Venue | Keywords |
---|---|---|
1996 | International Journal of Parallel, Emergent and Distributed Systems | graph partitioning,simulated annealing,local search,parallel computing,parallel computer |
Field | DocType | Citations |
Simulated annealing,Mathematical optimization,Heuristic,Computer science,Parallel algorithm,Theoretical computer science,Adaptive simulated annealing,Heuristics,Local search (optimization),Graph partition,Cost efficiency | Journal | 7 |
PageRank | References | Authors |
0.88 | 16 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ralf Diekmann | 1 | 281 | 28.99 |
Reinhard Lüling | 2 | 313 | 35.55 |
Burkhard Monien | 3 | 2199 | 279.35 |
Carsten Spräner | 4 | 7 | 0.88 |