Poslední úprava: doc. RNDr. Martin Balko, Ph.D. (11.09.2023)
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
Poslední úprava: 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.
Literatura
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (30.04.2019)
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
Sylabus -
Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (07.09.2023)
kernelization
bounded search trees
iterative compression
treewidth
the W-hierarchy
the exponential-time hypothesis
kernelization lower bounds
parameterized approximation
Poslední úprava: doc. Andreas Emil Feldmann, Dr. (24.09.2020)
