Studie o hamiltonovských grafech bodovala v Itálii
Článek o hamiltonovských grafech, jehož autory jsou doktorandka Nikola Jedličková a prof. Jan Kratochvíl z Katedry aplikované matematiky MFF UK, získal ocenění Best Paper Award na mezinárodní konferenci IWOCA 2024.
Na konferenci IWOCA (International Workshop on Combinatorial Algorithms) se každoročně scházejí výzkumníci, kteří se zabývají návrhy algoritmů pro nejrůznější kombinatorické problémy, jež jsou základem počítačových aplikací ve vědě, strojírenství i byznysu. Na 35. ročníku konference, který se začátkem července konal na italské Ischii, vystoupila také doktorandka Matfyzu Nikola Jedličková. Na setkání představila poznatky z článku On the Structure of Hamiltonian Graphs with Small Independence Number, který napsala společně se svým školitelem prof. Janem Kratochvílem. První autorka studie z Itálie přivezla ocenění Best Paper Award.
V oceněné publikaci podávají zástupci Informatické sekce Matfyzu strukturální popis situací, za kterých „husté grafy neobsahují tzv. hamiltonovskou cestu“. „Hamiltonovská cesta prochází v grafu všemi jeho vrcholy, a každým právě jednou. Jinak řečeno, je to nejúspornější možné propojení všech vrcholů grafu do souvislé procházky,“ vysvětlují autoři. Ne každý graf takové propojení umožňuje a pro obecné grafy je otázka existence hamiltonovské cesty efektivně neřešitelná (tzv. NP-úplná). „Náš předchozí výsledek ukazuje, že pro husté grafy (měřeno maximálním počtem vrcholů, mezi nimiž nevedou žádné hrany, tedy tzv. nezávislosti grafu) lze existenci hamiltonovské cesty rozhodnout v polynomiálním čase. To se do té doby nevědělo ani pro grafy nezávislosti 3. V oceněném článku jsme tyto polynomiální algoritmy doplnili explicitním popisem zakázaných situací, a to pro grafy nezávislosti 2, 3 a 4.“
OPMK
