Laplacian spectrum analysis and spanning tree algorithm for circuit partitioning problems

来源 :Science in China(Series F:Information Sciences) | 被引量 : 0次 | 上传用户:gaiwenru
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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. 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.
其他文献
In the course of the cryoplant modernization,a control network will be set up inorder to facilitate the control,the supervision,the centralized data acquisitio
The notion of No Free Lunch with Vanishing Risk (or NFLVR in short) w.r.t. admissible strategies depends on the choice of numeraire. Yan introduced the notion
Ribosome-inactivating proteins in Trichosanthes kirilowii having high anti-HIV activity can be efficiently obtained by culturing Trichosanthes kirilowii hairy
This paper is to solve several problems on the global attractivity of the zero solution of the nonautonomous difference equation xn+1 - xn + Pnxn-kn = 0, n ∈ Z
L2 estimates are obtained for some oscillatory singular integral operators with analytic phrases by using the technology of almost orthogonality, oscillatory es
The flashover of insulator strings occurring at normal working voltages under contaminated/polluted conditions, obviously deserves serious consideration. Though
The influence of growth pressure of GaN buffer layer on the properties of MOCVD GaN on α-Al2O3 has been investigated with the aid of a home-made in situ laser
将Feshbach-Kerman-Koonin(FKK)量子多步复合(MSC)理论推广至核子自旋为1/2,靶核自旋任意,在j -j表象严格处理角动量耦合,得到自旋为1/2的FKK-MSC公式. 进一步用光学模型吸收