|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Golovach, Petr (oponent) ; Proskurowski, Andrzej (oponent)
Tato práce se zabývá výpočetními problémy okolo grafových homomorfismů a příbuz- ných konceptů. Především se zabýváme složitostními dichotomiemi, které rozlišují mezi polynomiálními a NP-úplnými problémy. Výsledky tohoto typu jsou velmi populární, a to jak díky klasickému výsledku Hella a Nešetřila, tak i díky nedávnému vyřešení hypotézy o dichotomii pro problémy s omezujícími podmínkami (CSP). Práce se dělí na tři části, jejichž společným pojítkem je cíl prozkoumat složitost a následně určit dichotomii různých problémů speciálních typů či zobecnění grafových ho- momorfismů. První část se zabývá signed grafy, kde dokazujeme složitostní dichotomii listové, do- sud nezkoumané varianty homomorfismu pro případ, že cílový graf je strom anebo graf tzv. cyklově- nebo cestově-separovatelný. Druhá část se zabývá problémem grafového na- krytí, který je známý jak v algebraické, tak v algoritmické teorii grafů. Tato část práce si klade za cíl rozšířit zkoumání složitosti na grafy s povolenými vícenásobnými hranami, smyčkami a s půlhranami. Zde zkoumáme (a) klasifikaci složitosti pro jednovrcholové a dvouvrcholové cíle, (b) jaká je správná definice grafového nakrytí pro nesouvislé cíle a (c) co se stane, když přidáme do problému listové podmínky. Poslední část se zabývá acyklickými barveními a složitostí hledání...
|
host ::
RSS.