Linear and quadratic programming approaches for the general graph partitioning problem

Neng Fan, Panos M. Pardalos

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


The graph partitioning problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as a zero-one quadratic programming problem without the input of cardinalities. We also present three equivalent zero-one linear integer programming reformulations. Because of its importance in data biclustering, the bipartite graph partitioning is also studied. Several new methods to determine the number of subsets and the cardinalities are presented for practical applications. In addition, hierarchy partitioning and partitioning of bipartite graphs without reordering one vertex set, are studied.

Original languageEnglish (US)
Pages (from-to)57-71
Number of pages15
JournalJournal of Global Optimization
Issue number1
StatePublished - Sep 2010


  • Bipartite graph partitioning
  • Graph partitioning
  • Linear programming
  • Quadratic programming

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics
  • Business, Management and Accounting (miscellaneous)
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Linear and quadratic programming approaches for the general graph partitioning problem'. Together they form a unique fingerprint.

Cite this