A class of bounded approximation algorithms for graph partitioning

This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These a...

Full description

Saved in:
Bibliographic Details
Published in:Networks 1990-03, Vol.20 (2), p.181-195
Main Authors: Feo, Thomas A., Khellaf, Mallek
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Operational research and scientific management
Operational research. Management science
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds when k is large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing methods.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.3230200205