Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Ukažujeme, že problém rekonstrukce H-prostých grafů ze systémů okolí jejich vrcholů je polynomiálně řešitelný, pokud H je cesta nebo kružnice na nejvýše 4 vrcholech, a NP-úplný, pokud je to cesta nebo kružnice s alespoň 5 vrcholy.