Robust optimization of graph partitioning involving interval uncertainty

Neng Fan, Qipeng P. Zheng, Panos M. Pardalos

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


The graph partitioning problem consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. In this paper, robust optimization models with two decomposition algorithms are introduced to solve the graph partitioning problem with interval uncertain weights of edges. The bipartite graph partitioning problem with edge uncertainty is also presented. Throughout this paper, we make no assumption regarding the probability of the uncertain weights.

Original languageEnglish (US)
Pages (from-to)53-61
Number of pages9
JournalTheoretical Computer Science
StatePublished - Aug 17 2012


  • Benders decomposition
  • Bipartite graph partitioning
  • Graph partitioning
  • Robust optimization
  • Uncertainty

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Robust optimization of graph partitioning involving interval uncertainty'. Together they form a unique fingerprint.

Cite this