Spectral bounds for graph partitioning with prescribed partition sizes

Miguel Anjos, Jose Neto

Research output: Contribution to journalArticlepeer-review

Abstract

Given an undirected edge weighted graph, the graph partitioning problem consists in determining a partition of the node set of the graph into subsets of
prescribed sizes, so as to maximize the sum of the weights of the edges having
both endpoints in the same subset. We introduce a new class of bounds for
this problem relying on the full spectral information of the weighted adjacency
matrix A. The expression of these bounds involves the eigenvalues and particular geometrical parameters defined using the eigenvectors of A. A connection is established between these parameters and the maximum cut problem. We report computational results showing that the new bounds compare favorably with previous bounds in the literature.
Original languageEnglish
Pages (from-to)200-210
Number of pages11
JournalDiscrete Applied Mathematics
Volume269
Early online date25 Jun 2019
DOIs
Publication statusPublished - 30 Sep 2019

Fingerprint Dive into the research topics of 'Spectral bounds for graph partitioning with prescribed partition sizes'. Together they form a unique fingerprint.

Cite this