Publikace na Matematicko-fyzikální fakulta |
2006
Abstrakt
Ukazujeme, že max-toleranční grafy jsou průnikové grafy podobných trojúhelníků v rovině, a na základě této geometrické reprezentace dokazujeme, že jejich rozpoznáváníé je NP-těžké, ale maximální kliku lze nalézt v polynomálním čase.