Partitioning a graph into balanced connected classes: Formulations, separation and experiments

Flávio K. Miyazawa, Phablo F.S. Moura, Matheus J. Ota and Yoshiko Wakabayashi

European Journal of Operational Research, 2021, vol. 293, issue 3, 826-836

Abstract: This work addresses the balanced connectedk-partition problem (BCPk), which is formally defined as follows. Given a connected graph G=(V,E) with nonnegative weights on the vertices, find a partition {Vi}i=1k of V such that each class Vi induces a connected subgraph of G, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCPk. The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature.

Keywords: Integer programming; Branch-and-cut; Separation algorithm; Balanced partition; Connected partition (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720311218
Full text for ScienceDirect subscribers only

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:eee:ejores:v:293:y:2021:i:3:p:826-836

DOI: 10.1016/j.ejor.2020.12.059

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().