Locating the Eigenvalues for Graphs of Small Clique-Width

被引：3

作者：

Furer, Martin ^{[1
]}

Hoppen, Carlos ^{[2
]}

Jacobs, David P. ^{[3
]}

Trevisan, Vilmar ^{[2
]}

机构：

[1] Penn State Univ, Dept Comp Sci & Engn, State Coll, PA 16801 USA

[2] Univ Fed Rio Grande do Sul, Inst Matemat, Alegre, Brazil

[3] Clemson Univ, Sch Comp, Clemson, SC USA

来源：

LATIN 2018: THEORETICAL INFORMATICS | 2018年 / 10807卷

关键词：

Eigenvalues; Clique-width; Congruent matrices; Efficient algorithms; Parameterized algorithms; COGRAPHS; GRAMMARS;

D O I：

10.1007/978-3-319-77404-6_35

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：475 / 489

页数：15

共 22 条

[1] Eigenvalue location for chain graphs [J].

Alazemi, Abdullah ;

Andelic, Milica ;

Simic, Slobodan K. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 505 :194-210

[2]

[Anonymous], 1998, CONGR NUMER CONF J N

[3]

[Anonymous], 2001, Matrix Analysis and Applied Linear Algebra

[4]

Biyikoglu T, 2011, ARS COMBINATORIA, V100, P421

[5] LOCATING EIGENVALUES OF UNICYCLIC GRAPHS [J].

Braga, Rodrigo O. ;

Rodrigues, Virginia M. ;

Trevisan, Vilmar .

APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2017, 11 (02) :273-298

[6] HANDLE-REWRITING HYPERGRAPH GRAMMARS [J].

COURCELLE, B ;

ENGELFRIET, J ;

ROZENBERG, G .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (02) :218-270

[7] Upper bounds to the clique width of graphs [J].

Courcelle, B ;

Olariu, S .

DISCRETE APPLIED MATHEMATICS, 2000, 101 (1-3) :77-114

[8]

Courcelle B, 1997, HDB GRAPH GRAMMARS C, P313, DOI DOI 10.1142/9789812384720_

[9]

Fellows M. R., 2006, STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, P354, DOI 10.1145/1132516.1132568

[10]

Jacobs D. P, 2017, DISCRETE APPL MATH

← 1 2 3 →