Switching to Hedgehog-Free Graphs is NP-Complete

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10100401" target="_blank" >RIV/00216208:11320/11:10100401 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-20877-5_45" target="_blank" >http://dx.doi.org/10.1007/978-3-642-20877-5_45</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-20877-5_45" target="_blank" >10.1007/978-3-642-20877-5_45</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Switching to Hedgehog-Free Graphs is NP-Complete
Popis výsledku v původním jazyce
We study the problem of deciding if, for a fixed graph H, a given graph is switching-equivalent to an H-free graph. In all cases of H that have been solved so far, the problem is decidable in polynomial time. We give infinitely many graphs H such that the problem is NP-complete, thus solving an open problem [Kratochvíl, Nešetřil and Zýka, Ann. Discrete Math. 51 (1992)].
Název v anglickém jazyce
Switching to Hedgehog-Free Graphs is NP-Complete
Popis výsledku anglicky
We study the problem of deciding if, for a fixed graph H, a given graph is switching-equivalent to an H-free graph. In all cases of H that have been solved so far, the problem is decidable in polynomial time. We give infinitely many graphs H such that the problem is NP-complete, thus solving an open problem [Kratochvíl, Nešetřil and Zýka, Ann. Discrete Math. 51 (1992)].

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—

Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)