Approximation algorithms for some graph partitioning problems.
2000
This paper considers problems of the following type: given an edgeweighted k-colored input graph with maximum color class size c, nd a minimum or maximum c-way cut such that each color class is totally partitioned. Equivalently, given a weighted complete k-partite graph, cover its vertices with a minimum number of disjoint cliques in such a way that the total weight of the cliques is maximized or minimized. Our study was motivated by some work called the index domain alignment problem [6], which shows its relevance to optimization of distributed computation. Solutions of these problems also have applications in logistics [3] and manufacturing systems [10]. In this paper, we design some approximation algorithms by extending the matching algorithms to these problems. Both theoretical and experimental results show that the algorithms we designed produce good approximations.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
10
References
25
Citations
NaN
KQI