Multi-way clustering and biclustering by the Ratio cut and Normalized cut in graphs

Neng Fan, Panos M. Pardalos

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


In this paper, we consider the multi-way clustering problem based on graph partitioning models by the Ratio cut and Normalized cut. We formulate the problem using new quadratic models. Spectral relaxations, new semidefinite programming relaxations and linearization techniques are used to solve these problems. It has been shown that our proposed methods can obtain improved solutions. We also adapt our proposed techniques to the bipartite graph partitioning problem for biclustering.

Original languageEnglish (US)
Pages (from-to)224-251
Number of pages28
JournalJournal of Combinatorial Optimization
Issue number2
StatePublished - Feb 2012


  • Biclustering
  • Clustering
  • Graph partitioning
  • Normalized cut
  • Quadratically constrained programming
  • Ratio cut
  • Semidefinite programming
  • Spectral relaxation

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Multi-way clustering and biclustering by the Ratio cut and Normalized cut in graphs'. Together they form a unique fingerprint.

Cite this