Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: The node capacitated graph partitioning problem: A computational study
Author: Ferreira, CE
Martin, A
de Souza, C
Weismantel, R
Wolsey, LA
Abstract: In this paper we consider the problem of k-partitioning the nodes of a graph with capacity restrictions on the sum of the node wrights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities. we present a variety of separation heuristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Subject: branch-and-cut algorithm
compiler design
finite element method
graph partitioning
layout of electronic circuits
separation heuristics
Country: EUA
Editor: Springer
Citation: Mathematical Programming. Springer, v. 81, n. 2, n. 229, n. 256, 1998.
Rights: fechado
Identifier DOI: 10.1007/BF01581107
Date Issue: 1998
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000073078500006.pdf1.92 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.