TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 09.02.2017

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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



 

Date
Speaker
Location
Language
09.02.2017
16:15
Dieaa Al Aied
TEL 512
English

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe