Introduction to Parameterized Algorithms - NTIN103

• Title in English: Introduction to Parameterized Algorithms
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2018 to 2019
• Semester: winter
• E-Credits: 6
• Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
• Capacity: unlimited
• Min. number of students: unlimited
• State of the course: taught
• Language: English
• Teaching methods: full-time
• Additional information: https://sites.google.com/site/aefeldmann/teaching/introduction-to-parameterized-algorithms-winter-2018
• Guarantor: Andreas Emil Feldmann, Dr.
• Class: DS, teoretická informatika; DS, diskrétní modely a algoritmy; Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Diskrétní modely a algoritmy
• Classification: Informatics > Discrete Mathematics, Optimalization, Theoretical Computer Science

Annotation

English

Last update: T_KAM (18.04.2017)

Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the time is kept low. Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is typically small.

Czech

Last update: Mgr. Jan Kynčl, Ph.D. (29.04.2019)

Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the time is kept low. Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is typically sma

Literature

Last update: T_KAM (18.04.2017)

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6

Syllabus

Last update: Andreas Emil Feldmann, Dr. (03.09.2018)

• kernelization

• bounded search trees

• iterative compression

• treewidth

• the W-hierarchy

• the exponential-time hypothesis

• kernelization lower bounds

• parameterized approximation