Studie o hamiltonovských grafech bodovala v Itálii

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