TY - GEN
T1 - Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
AU - Fürer, Martin
AU - Hoppen, Carlos
AU - Trevisan, Vilmar
N1 - Funding Information:
Carlos Hoppen: CNPq 308054/2018-0 and FAPERGS 19/2551-0001727-8. Vilmar Trevisan: CNPq 409746/2016-9 and 303334/2016-9, CAPES-PRINT 88887.467572/2019-00, and FAPERGS 17/2551-0001.
Publisher Copyright:
© Martin Fürer, Carlos Hoppen, and Vilmar Trevisan; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/6/1
Y1 - 2020/6/1
N2 - Let M = (mij) be a symmetric matrix of order n and let G be the graph with vertex set {1, . . ., n} such that distinct vertices i and j are adjacent if and only if mij 6= 0. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to M. If G is given with a tree decomposition T of width k, then this can be done in time O(k|T | + k2n), where |T | denotes the number of nodes in T .
AB - Let M = (mij) be a symmetric matrix of order n and let G be the graph with vertex set {1, . . ., n} such that distinct vertices i and j are adjacent if and only if mij 6= 0. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to M. If G is given with a tree decomposition T of width k, then this can be done in time O(k|T | + k2n), where |T | denotes the number of nodes in T .
UR - http://www.scopus.com/inward/record.url?scp=85089351898&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089351898&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2020.52
DO - 10.4230/LIPIcs.ICALP.2020.52
M3 - Conference contribution
AN - SCOPUS:85089351898
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
A2 - Czumaj, Artur
A2 - Dawar, Anuj
A2 - Merelli, Emanuela
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
Y2 - 8 July 2020 through 11 July 2020
ER -