Partitioning Generic Graphs into k Regions

D. Portugal and R. P. Rocha

In Proc. of 6th Iberian Congress on Numerical Methods in Engineering (CMNE’2011), Coimbra, Portugal, Jun. 14-17, 2011.

Abstract

Graph partitioning is a classical graph theory problem that has proven to be NP-hard. Most of the research in literature has focused its attention on a particular case of the problem called the graph bisection problem, where k = 2, such that the parts have approximately equal weight and minimizing the size of the edge cut. In this article, we describe how to obtain balanced partitioning on a given undirected, connected and weighted graph into an arbitrary number k of regions (subgraphs), by hierarchically employing a multilevel bisection algorithm not only in the general graph, but also in the originated subgraphs. Due to the application chosen for this study, the partition consists of k subgraphs, which are subsets of vertices in the same region, not intended to be totally disjoint, sharing at least one vertex with another subgraph near their borders.

Index Terms — Graph theory, balanced partition, bisection, subgraphs.

Full text

You may ask Rui Rocha for an electronic copy of this publication’s full text by e-mail:
.

Please select for your message’s subject ‘Requesting Rui Rocha’s electronic copy’ and include on the message’s body your full name, title and affiliation, why do you need to access the publication and the BibTeX information below.

BibTeX

@INPROCEEDINGS(Portugal_Rocha_11b,

AUTHOR = "Portugal, D. and Rocha, R.P.",

TITLE = "Partitioning Generic Graphs into k Regions",

BOOKTITLE = "In Proc. of 6th Iberian Congress on Numerical Methods in Engineering (CMNE’2011)",

ADDRESS = "Coimbra, Portugal",

YEAR = "2011",

MONTH = "Jun."

)

(top of the page)

Last update: 14/06/2011