Name
Abstract | ||
|---|---|---|
The k-partition problem seeks to cluster the vertices of an edge-weighted graph, G = (V,E), into k sets of \V\/k vertices each, such that the total weight of the edges having both endpoints in the same cluster is maximized. Bottom-up type heuristics based on matchings are presented for this problem. These heuristics are shown to yield solutions that are at least one-half the weight of the optimal solution for k equal to \V\/3 and \V\/4. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1287/opre.40.1.S170 | Operations Research |
Field | DocType | Volume |
Graph theory,Partition problem,Approximation algorithm,Discrete mathematics,Graph,Mathematical optimization,Combinatorics,Vertex (geometry),Heuristics,Graph partition,Mathematics,One half | Journal | 40 |
Issue | ISSN | Citations |
S1 | 0030-364X | 20 |
PageRank | References | Authors |
5.21 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas A. Feo | 1 | 163 | 23.88 |
| Olivier Goldschmidt | 2 | 20 | 5.21 |
| Mallek Khellaf | 3 | 52 | 10.65 |