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 , 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“. 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á).

https://www.mff.cuni.cz/cs/verejnost/aktuality/studie-o-hamiltonovskych-grafech-bodovala-v-italii