| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/11:00053105 |
| Název v původním jazyce | Parameterized Problems Related to Seidel's Switching |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor | BA - Obecná matematika |
| Rok uplatnění | 2011 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 2 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | Jimp - Článek v impaktovaném časopise evidovaném ve Web of Science |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Výsledek hodnocený již v předchozím hodnocení, body se přebírají |
| Bodové ohodnocení | 16,022 |
| Faktor korekce | 100,9 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 16,171 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Univerzita Karlova v Praze / Matematicko-fyzikální fakulta | ano | 75,0 % | 12,017 | 12,128 |
| Masarykova univerzita / Fakulta informatiky | ano | 25,0 % | 4,006 | 4,043 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 4 |
| Počet domácích tvůrců | 1 |
| Tvůrce | Hliněný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 7595646) |
| Tvůrce | Jelínková Eva (státní příslušnost: CZ - Česká republika) |
| Tvůrce | Kratochvíl Jan (státní příslušnost: CZ - Česká republika) |
| Tvůrce | Suchý Ondřej (státní příslušnost: CZ - Česká republika) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most $k$ edges, to a graph of maximum degree at most $k$, to a $k$-regular graph, or to a graph with minimum degree at least $k$ are fixed parameter tractable problems, where $k$ is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is $W[1]$-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. |
| Klíčová slova | graph; Seidel switching |
| Kód UT ISI | 000290721600002 |
| Název periodka | Discrete Mathematics & Theoretical Computer Science |
| Rozsah stran | 19-42 |
| ISSN | 1365-8050 |
| Svazek periodika | 13 |
| Číslo periodika v rámci uvedeného svazku | 2 |
| Stát vydavatele periodika | FR - Francouzská republika |
| Počet stran výsledku | 24 |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2012 |
| Systémové označení dodávky dat | RIV12-MSM-14330___/01:1 |
| Specifikace | RIV/00216224:14330/11:00053105!RIV12-MSM-14330___ |
| Kontrolní kód | [7E0E87093C06] |
| Další výskyty tohoto výsledku od jiných předkladatelů |
| Další předkladatel | Univerzita Karlova v Praze / Matematicko-fyzikální fakulta |
| Dodáno MŠMT v roce 2012 | Záznam s identifikačním kódem RIV/00216208:11320/11:10100314 v dodávce dat RIV12-MSM-11320___/01:1 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | 1M0545 - Institut Teoretické Informatiky (2005-2011, MSM/1M) |
| Výzkumný záměr | MSM0021620838 - Moderní metody, struktury a systémy informatiky (2005-2011, MSM) |
| Výzkumný záměr | MSM0021622419 - Vysoce paralelní a distribuované výpočetní systémy (2005-2011, MSM) |