direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Fast Dynamic Graph Algorithms for Parameterized Problems

Dieaa Al Aied (TU Berlin)


Fully dynamic graph is a data structure that supports edge insertions and deletions and answers problem specific queries. In this talk, I’m gonna talk about dynamic graphs for Vertex Cover and Cluster Vertex Deletion parameterized by the solution size k. These dynamic graphs achieve almost the best possible update time O(poly(k) log(n)) and the query time O(f(poly(k), k)), where f(n, k) is the time complexity of any static graph algorithm for the problems. We obtain these results by dynamically maintaining an approximate solution which can be used to construct a small problem kernel.

The talk is based on the paper by Iwata and Oka [SWAT 2014].


Dieaa Al Aied
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras