TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 07.02.2019

isti-logo

Page Content

to Navigation

Algebraic Techniques: Sieves & Multivariate Polynomials

Yamen Ali (TU Berlin)

The talk is about how to exploit algebraic techniques in order to achieve parameterized algorithms.
The inclusion-exclusion principle and its application to the problem of Counting Hamiltonian Cycles in directed graphs will be presented.
Furthermore, an one-sided error Monte Carlo algorithm for k-Path based on evaluating multivariate polynomials will be explained that leads to a running time of 2^k n^O(1) and polynomial space.

The talk is based on Chapter 10 of the book 'Parameterized Algorithms' by Cygan et al. (2015).

 

Date
Speaker
Location
Language
07.02.2019
16:15
Yamen Ali
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe