Parametrizovaná a klasická složitost kombinatorických problémů
| Thesis title in Czech: | Parametrizovaná a klasická složitost kombinatorických problémů |
|---|---|
| Thesis title in English: | Parameterized and classical complexity of combinatorial problems |
| Key words: | výpočetní složitost|třídy grafů |
| English key words: | comutational complexity|graph classes |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | dissertation |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Jiří Fiala, Ph.D. |
| Author: |
| Guidelines |
| The goal of the thesis to study the computational complexity of some classical combinatorial optimization problem (coloring and its variants, independence, dominance problems, connectivity, Hamiltonicity paths etc.) with respect to specific classes. If possible, the characterization could be done with respect to some natural parameter in the context, e.g. the size of the solution, a width / dimension parameter, a parameter related to the geometric representation of the graph etc.
|
| References |
| Literature
R. Diestel: Graph Theory, Springer-Verlag (1997) M. Cygan et al: Parameterized Algorithms, Springer-Verlag (2016) C. H. Papadimitriou: Computational Complexity, Addison-Wesley (1994) R. G. Downey, M. R. Fellows: Parameterized Complexity, Springer-Verlag (1999) M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979) further journal literature from the field |