Locating the eigenvalues for graphs of small clique-width

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

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

Locating the eigenvalues for graphs of small clique-width

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

Eberly College of Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

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²n). This allows to quickly tell the number of eigenvalues in a given interval.

Original language	English (US)
Title of host publication	LATIN 2018
Subtitle of host publication	Theoretical Informatics - 13th Latin American Symposium, Proceedings
Editors	Miguel A. Mosteiro, Michael A. Bender, Martin Farach-Colton
Publisher	Springer Verlag
Pages	475-489
Number of pages	15
ISBN (Print)	9783319774039
DOIs	https://doi.org/10.1007/978-3-319-77404-6_35
State	Published - 2018
Event	13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 - Buenos Aires, Argentina Duration: Apr 16 2018 → Apr 19 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10807 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Symposium on Latin American Theoretical Informatics, LATIN 2018
Country/Territory	Argentina
City	Buenos Aires
Period	4/16/18 → 4/19/18

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Fürer, M., Hoppen, C., Jacobs, D. P., & Trevisan, V. (2018). Locating the eigenvalues for graphs of small clique-width. In M. A. Mosteiro, M. A. Bender, & M. Farach-Colton (Eds.), LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings (pp. 475-489). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-77404-6_35

Fürer, Martin ; Hoppen, Carlos ; Jacobs, David P. et al. / Locating the eigenvalues for graphs of small clique-width. LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. editor / Miguel A. Mosteiro ; Michael A. Bender ; Martin Farach-Colton. Springer Verlag, 2018. pp. 475-489 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{139d9cf47120436881b43cd7c2f72efe,

title = "Locating the eigenvalues for graphs of small clique-width",

abstract = "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(k2n). This allows to quickly tell the number of eigenvalues in a given interval.",

author = "Martin F{\"u}rer and Carlos Hoppen and Jacobs, {David P.} and Vilmar Trevisan",

note = "Funding Information: M. F{\"u}rer—Research supported in part by NSF Grant CCF-1320814. D. P. Jacobs and V. Trevisan—Work supported by Science without Borders CNPq - Grant 400122/2014-6, Brazil.; 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

year = "2018",

doi = "10.1007/978-3-319-77404-6_35",

language = "English (US)",

isbn = "9783319774039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "475--489",

editor = "Mosteiro, {Miguel A.} and Bender, {Michael A.} and Martin Farach-Colton",

booktitle = "LATIN 2018",

address = "Germany",

}

Fürer, M, Hoppen, C, Jacobs, DP & Trevisan, V 2018, Locating the eigenvalues for graphs of small clique-width. in MA Mosteiro, MA Bender & M Farach-Colton (eds), LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10807 LNCS, Springer Verlag, pp. 475-489, 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018, Buenos Aires, Argentina, 4/16/18. https://doi.org/10.1007/978-3-319-77404-6_35

Locating the eigenvalues for graphs of small clique-width. / Fürer, Martin; Hoppen, Carlos; Jacobs, David P. et al.
LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. ed. / Miguel A. Mosteiro; Michael A. Bender; Martin Farach-Colton. Springer Verlag, 2018. p. 475-489 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Locating the eigenvalues for graphs of small clique-width

AU - Fürer, Martin

AU - Hoppen, Carlos

AU - Jacobs, David P.

AU - Trevisan, Vilmar

N1 - Funding Information: M. Fürer—Research supported in part by NSF Grant CCF-1320814. D. P. Jacobs and V. Trevisan—Work supported by Science without Borders CNPq - Grant 400122/2014-6, Brazil.

PY - 2018

Y1 - 2018

N2 - 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(k2n). This allows to quickly tell the number of eigenvalues in a given interval.

AB - 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(k2n). This allows to quickly tell the number of eigenvalues in a given interval.

UR - http://www.scopus.com/inward/record.url?scp=85045392768&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045392768&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85045392768

SN - 9783319774039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 475

EP - 489

BT - LATIN 2018

A2 - Mosteiro, Miguel A.

A2 - Bender, Michael A.

A2 - Farach-Colton, Martin

PB - Springer Verlag

T2 - 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018

Y2 - 16 April 2018 through 19 April 2018

ER -

Fürer M, Hoppen C, Jacobs DP, Trevisan V. Locating the eigenvalues for graphs of small clique-width. In Mosteiro MA, Bender MA, Farach-Colton M, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Springer Verlag. 2018. p. 475-489. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-77404-6_35

Locating the eigenvalues for graphs of small clique-width

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this