Eigenvalue location in graphs of small clique-width

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

doi:10.1016/j.laa.2018.09.015

Eigenvalue location in graphs of small clique-width

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

Eberly College of Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

Finding a diagonal matrix congruent to A−cI for constants c, where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k-expression is known, then diagonalization can be done in time O(poly(k)n) where n is the order of G.

Original language	English (US)
Pages (from-to)	56-85
Number of pages	30
Journal	Linear Algebra and Its Applications
Volume	560
DOIs	https://doi.org/10.1016/j.laa.2018.09.015
State	Published - Jan 1 2019

All Science Journal Classification (ASJC) codes

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.laa.2018.09.015

Cite this

@article{edb786db4be14454b39cec69a29b79b8,

title = "Eigenvalue location in graphs of small clique-width",

abstract = "Finding a diagonal matrix congruent to A−cI for constants c, where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k-expression is known, then diagonalization can be done in time O(poly(k)n) where n is the order of G.",

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

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",

year = "2019",

month = jan,

day = "1",

doi = "10.1016/j.laa.2018.09.015",

language = "English (US)",

volume = "560",

pages = "56--85",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Eigenvalue location in graphs of small clique-width

AU - Fürer, Martin

AU - Hoppen, Carlos

AU - Jacobs, David P.

AU - Trevisan, Vilmar

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Finding a diagonal matrix congruent to A−cI for constants c, where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k-expression is known, then diagonalization can be done in time O(poly(k)n) where n is the order of G.

AB - Finding a diagonal matrix congruent to A−cI for constants c, where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k-expression is known, then diagonalization can be done in time O(poly(k)n) where n is the order of G.

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

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

U2 - 10.1016/j.laa.2018.09.015

DO - 10.1016/j.laa.2018.09.015

M3 - Article

AN - SCOPUS:85053827442

SN - 0024-3795

VL - 560

SP - 56

EP - 85

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Eigenvalue location in graphs of small clique-width

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this