direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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

Zusatzinformationen / Extras