CORAL Working Papers,
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

22 pages, November 3, 2005

Full text files

L_2005_02.pdf  

Download statistics

• University of Aarhus, Aarhus School of Business, Department of Business Studies
• Home page for this series

Questions (including download problems) about the papers in this series should be directed to Helle Vinbaek Stenholt ()
Report other problems with accessing this service to Sune Karlsson ().

RePEc:hhb:aarbls:2005-002This page generated on 2024-09-13 22:18:12.