Jakub Balabán

Twin-Width: Parameterized Algorithms and Structural Properties

Školitel: prof. RNDr. Petr Hliněný, Ph.D.

Instituce: Masaryk University, Faculty of Informatics

Obor: Computer Science

 

O projektu

Cílem projektu je zkoumat twin-width, což relativně nový grafový parametr. Je znám algoritmus, který na grafech s malou twin-width efektivně vyhodnotí libovolnou formuli prvořádové logiky. Tento algoritmus ale vyžaduje, aby byl spolu se vstupním grafem dodán certifikát malé twin-width. Hlavním cílem projektu tedy je navrhnout algoritmy, které by tyto certifikáty počítaly.

 

Proč dělám vědu?

Na vědě má rád, že se můžu pořád učit nové věci. Zároveň je to kreativní práce: dělat výzkum v matematice je svého druhu umění. Navíc rád píšu, což je důležité, protože důležité je umět nové poznatky srozumitelně sepsat. Zároveň rád cestuji a poznávám nová místa, což v rámci svého doktorátu můžu díky konferencím a letním školám.

 

Proč mám rád/a Brno

Líbí se mi centrum, které se dá projít pěšky a které není přeplněno turisty. Také oceňuji veřejnou dopravu, díky které se člověk dostane odkudkoli kamkoli. Celkově má Brno ideální velikost: nic mi tu nechybí, ale zároveň není velkoměsto.