Polyhedral Computations for the Simple Graph Partitioning Problem

Michael M. Sørensen (mim@asb.dk)
Additional contact information
Michael M. Sørensen: Department of Business Studies, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark, http://www.asb.dk/staff/bs/mim.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D

No L-2005-02, CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies

Abstract: The simple graph partitioning problem is to partition an edge-weighted graph into mutually disjoint subgraphs, each containing no more than b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we present a branch-and-cut algorithm for the problem that uses several classes of facet-defining inequalities as cuttingplanes. These are b-tree, clique, cycle with ear, multistar, and S, Tinequalities. Descriptions of the separation procedures that are used for these inequality classes are also given. In order to evaluate the usefulness of the inequalities and the overall performance of the branch-and-cut algorithm several computational experiments are conducted. We present some of the results of these experiments.

Keywords: Branch-and-cut algorithm; Facets; Graph partitioning; Multicuts; Separation procedures (search for similar items in EconPapers)
Pages: 22 pages
Date: 2005-11-03
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.hha.dk/afl/wp/log/L_2005_02.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.hha.dk:80 (No such host is known. )

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhb:aarbls:2005-002

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Helle Vinbaek Stenholt (hes@asb.dk this e-mail address is bad, please contact repec@repec.org).