Porovnávání univerzálních nakrytí v polynomiálním čase

Abstrakt

Ukazujeme, že univezální nakrytí konečných grafů lze porovnávat v polynomiálním čase podle existence lokálně injekivních či surjektivních homomorfismů.

Klíčová slova

• univerzální nakrytí
• výpočetní složitost