Algorithms for graph partitioning problems by means of eigenspace relaxations

Chih Chien Tu, Ce Kuen Shieh, Hsuanjen Cheng

研究成果: Article同行評審

3 引文 斯高帕斯(Scopus)

摘要

Graph partitioning problems are NP-hard problems and very important in VLSI design. We study relations among several eigenvalue bounds and algorithms for graph partitioning problems. Also, we design an algorithm for the problems which performs the following: first it computes the k largest eigenvalues of the affine symmetric matrix function to attain Donath-Hoffman bound; then it calculates a relaxed partition which is an array constant factor of an eigenspace associated with k eigenvalues; finally it generates an actual partition from the relaxed solution of a method similar to Boppana's algorithm. To compute optimal eigenvalue bounds, one needs to solve eigenvalue optimization problems which minimize the sum of the k largest eigenvalues of the nonsmooth functions. We use a subgradient method to compute the Donath-Hoffman eigenvalue bound. Numerical results indicate that although the Donath-Hoffman bound is not tight for graph partitioning problems, our algorithm can generate optimal partitions.

原文English
頁(從 - 到)86-104
頁數19
期刊European Journal of Operational Research
123
發行號1
DOIs
出版狀態Published - 2000 五月 16

All Science Journal Classification (ASJC) codes

  • 電腦科學(全部)
  • 建模與模擬
  • 管理科學與經營研究
  • 資訊系統與管理

指紋

深入研究「Algorithms for graph partitioning problems by means of eigenspace relaxations」主題。共同形成了獨特的指紋。

引用此