期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Laplacian spectrum analysis and spanning tree algorithm for circuit partitioning problems

Laplacian spectrum analysis and spanning tree algorithm for circuit partitioning problems
原文传递
导出
摘要 The spectrum of a graph is the set of all eigenvalues of the Laplacian matrix of the graph. There is a closed relationship between the Laplacian spectrum of graphs and some properties of graphs such as connectivity. In the recent years Laplacian spectrum of graphs has been widely applied in many fields. The application of Laplacian spectrum of graphs to circuit partitioning problems is reviewed in this paper. A new criterion of circuit partitioning is proposed and the bounds of the partition ratio for weighted graphs are also presented. Moreover, the deficiency of graph-partitioning algorithms by Laplacian eigenvectors is addressed and an algorithm by means of the minimal spanning tree of a graph is proposed. By virtue of taking the graph structure into consideration this algorithm can fulfill general requirements of circuit partitioning. The spectrum of a graph is the set of all eigenvalues of the Laplacian matrix of the graph. There is a closed relationship between the Laplacian spectrum of graphs and some properties of graphs such as connectivity. In the recent years Laplacian spectrum of graphs has been widely applied in many fields. The application of Laplacian spectrum of graphs to circuit partitioning problems is reviewed in this paper. A new criterion of circuit partitioning is proposed and the bounds of the partition ratio for weighted graphs are also presented. Moreover, the deficiency of graph-partitioning algorithms by Laplacian eigenvectors is addressed and an algorithm by means of the minimal spanning tree of a graph is proposed. By virtue of taking the graph structure into consideration this algorithm can fulfill general requirements of circuit partitioning.
作者 杨华中 胡冠章
机构地区 Department of Electronic Engineering Department of Mathematical Science
出处 《Science in China(Series F)》 2003年第6期459-465,共7页 中国科学（F辑英文版）
基金 This work was supported in part by the National Natural Science Foundation of China(Grant Nos.60025101 and 90207001) by the National Basic Research Priorities Program(Contract No.G1999032903).
关键词 graph partitioning Laplacian spectrum of a graph partition ratio spanning tree of a graph. graph partitioning, Laplacian spectrum of a graph, partition ratio, spanning tree of a graph.
分类号 TN702 [电子电信—电路与系统]
  • 相关文献

参考文献16

  • 1[1]Biggs, N. L., Algebraic Graph Theory, Cambridge: Cambridge University Press, first edition 1974, second edition, 1993.
  • 2[2]Grone, R., Merris, R., Sunder, V., The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 1990, 11(2): 218-238.
  • 3[3]Merris, R., Laplacian matrices of graphs: A survey, Linear Algebra and Its Applications, 1994, 197-198: 143-176.
  • 4[4]Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, London: The Macmillan Press LTD, 1976.
  • 5[5]Hu, G. Z., Handbook on Modern Applied Mathematics, Volume of Discrete Mathematics: Combinatorics and Graph Theory (in Chinese), Beijing: Tsinghua University Press, 2002.
  • 6[6]Alpert, C. J., Kahgn, A. B., Recent directions in netlist partitioning-A survey, Integration, 1995, 19: 1-81.
  • 7[7]Fiedler, M., Algebraic connectivity of graphs, Czechoslovak Math. J., 1973, 23(98): 298-305.
  • 8[8]Hagen, L., Kahng, A. B., New spectral methods for ratio cut partition and clustering, IEEE Trans. Computer-Aided design, 1992, 11: 1074-1085.
  • 9[9]Yang, H. Z., Hu, G. Z., Wang, H., Criterion for reducing power consumption by means of ratio-cut circuit partitioning, Electronic Letters, 3rd August, 2000, 36(16): 1346-1347.
  • 10[10]Lengauer, T., Combinatorial Algorithms for Integrated Circuit Layout, New York: Wiley-Teubner, 1990.
Science in China(Series F)
2003年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部