A New Heuristic for Partitioning the Nodes of a Graph
Authors:
- Earl R. BarnesEBEarl R. Barnes
- Anthony VannelliAVAnthony Vannelli
- James Q. WalkerJWJames Q. Walker
- 1 August 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 1 (3) , 299-305
Abstract
There is a class of graph partitioning algorithms which improve an initial partition by interchanging nodes between the subsets of the initial partition. These algorithms tend to require long running times because usually many trials must be made before the right combination of nodes to interchange is found. In this paper we describe a fast procedure for determining sets of nodes to interchange in order to improve an initial partition.Keywords
This publication has 6 references indexed in Scilit:
- The indefinite zero-one quadratic problemDiscrete Applied Mathematics, 1984
- An Algorithm for Partitioning the Nodes of a GraphSIAM Journal on Algebraic Discrete Methods, 1982
- Optimal Decomposition of Large-Scale NetworksIEEE Transactions on Systems, Man, and Cybernetics, 1979
- A Heuristic Procedure for the Partitioning and Mapping of Computer Logic GraphsIEEE Transactions on Computers, 1971
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- A study of the effect of user program optimization in a paging system1967