1 Search Results for "Trevisan, Vilmar"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.52
Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth

Authors: Martin Fürer, Carlos Hoppen, and Vilmar Trevisan

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Let M = (m_{ij}) 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 m_{ij} ≠ 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 𝒯 of width k, then this can be done in time O(k|𝒯| + k² n), where |𝒯| denotes the number of nodes in 𝒯.
Cite as

Martin Fürer, Carlos Hoppen, and Vilmar Trevisan. Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{furer_et_al:LIPIcs.ICALP.2020.52,
  author =	{F\"{u}rer, Martin and Hoppen, Carlos and Trevisan, Vilmar},
  title =	{{Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.52},
  URN =		{urn:nbn:de:0030-drops-124590},
  doi =		{10.4230/LIPIcs.ICALP.2020.52},
  annote =	{Keywords: Treewidth, Diagonalization, Eigenvalues}
}
  • Refine by Author
  • 1 Fürer, Martin
  • 1 Hoppen, Carlos
  • 1 Trevisan, Vilmar

  • Refine by Classification
  • 1 Computing methodologies → Linear algebra algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 Diagonalization
  • 1 Eigenvalues
  • 1 Treewidth

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact