Locating the Eigenvalues for Graphs of Small Clique-Width.

Martin Fürer,Carlos Hoppen,David P. Jacobs,Vilmar Trevisan

Lecture Notes in Computer Science（2018）

引用 1|浏览21

暂无评分

摘要

It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to A-cI for constants c, where A is the adjacency matrix of the graph G of order n, can be computed in time O(k(2)n). This allows to quickly tell the number of eigenvalues in a given interval.

查看译文

关键词

Eigenvalues,Clique-width,Congruent matrices,Efficient algorithms,Parameterized algorithms

AI 理解论文

溯源树

样例

生成溯源树，研究论文发展脉络

Chat Paper

正在生成论文摘要