Laplacian spectrum analysis and spanning tree algorithm for circuit partitioning problems |
| |
Authors: | Email author" target="_blank">Yang?Huazhong?Email author Hu?Guanzhang |
| |
Affiliation: | 1. Department of Electronic Engineering, Tsinghua University, Beijing 100084, China 2. Department of Mathematical Science, Tsinghua University, Beijing 100084, China |
| |
Abstract: | 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. |
| |
Keywords: | graph partitioning Laplacian spectrum of a graph partition ratio spanning tree of a graph |
本文献已被 CNKI 万方数据 SpringerLink 等数据库收录! |