DROPS

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.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}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2017.14

Multi-Clique-Width

Authors: Martin Fürer

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract

Multi-clique-width is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode exponentially compared to tree-width. Efficient algorithms based on multi-clique-width are still possible for interesting tasks like computing the independent set polynomial or testing c-colorability. In particular, c-colorability can be tested in time linear in n and singly exponential in c and the width k of a given multi-k-expression. For these tasks, the running time as a function of the multi-clique-width is the same as the running time of the fastest known algorithm as a function of the clique-width. This results in an exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for many graphs. This gap shows up when the tree-width is basically equal to the multi-clique width as well as when the tree-width is not bounded by any function of the clique-width.

Cite as

Martin Fürer. Multi-Clique-Width. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{furer:LIPIcs.ITCS.2017.14,
  author =	{F\"{u}rer, Martin},
  title =	{{Multi-Clique-Width}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.14},
  URN =		{urn:nbn:de:0030-drops-81775},
  doi =		{10.4230/LIPIcs.ITCS.2017.14},
  annote =	{Keywords: clique-width, parameterized complexity, tree-width, independent set polynomial, graph coloring}
}

Search Results

Documents authored by Fürer, Martin

Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth

Abstract

Cite as

Multi-Clique-Width

Abstract

Cite as

Thanks for your feedback!

Could not send message