RIV/00216208:11320/11:10100314 - Parameterized Problems Related to Seidel''s Switching (2011)

Údaje o výsledku
Identifikační kódRIV/00216208:11320/11:10100314
Název v původním jazyceParameterized Problems Related to Seidel''s Switching
DruhJ - Článek v odborném periodiku
Jazykeng - angličtina
OborIN - Informatika
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ýsledku2
Údaje z Hodnocení výsledků výzkumných organizací 2014
Výsledek byl hodnocen v Pilíři I
Rozsah vyřazení výsledkuTento 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ýsledkuVýsledek hodnocený již v předchozím hodnocení, body se přebírají
Bodové ohodnocení16,022
Faktor korekce100,9 %
Body (upravené podle přílohy č. 8 Metodiky)16,171
Rozdělení výsledku mezi předkladatele
OrganizaceVýzkumná organizace?PodílBodyBody (upravené podle přílohy č. 8 Metodiky)
Univerzita Karlova v Praze / Matematicko-fyzikální fakultaano75,0 %12,01712,128
Masarykova univerzita / Fakulta informatikyano25,0 %4,0064,043
Tvůrci výsledku
Počet tvůrců celkem4
Počet domácích tvůrců3
TvůrceKratochvíl Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 1123580)
TvůrceJelínková Eva (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 5997011)
TvůrceSuchý Ondřej (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 1039709)
TvůrceHliněný Petr (státní příslušnost: CZ - Česká republika)
Údaje blíže specifikující výsledek
Popis v původním jazyceSeidel'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á slovaParameterized Complexity; Computational Complexity; Seidel's Switching
Kód UT ISI000290721600002
Název periodkaDiscrete Mathematics and Theoretical Computer Science
Rozsah stran19-42
ISSN1365-8050
Svazek periodika13
Číslo periodika v rámci uvedeného svazku2
Stát vydavatele periodikaFR - Francouzská republika
Počet stran výsledku24
Adresa www stránky s výsledkemhttp://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1531
Údaje o tomto záznamu o výsledku
PředkladatelUniverzita Karlova v Praze / Matematicko-fyzikální fakulta
DodavatelMSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT)
Rok sběru2012
Systémové označení dodávky datRIV12-MSM-11320___/01:1
SpecifikaceRIV/00216208:11320/11:10100314!RIV12-MSM-11320___
Kontrolní kód[0EF339C46EA0]
Další výskyty tohoto výsledku od jiných předkladatelů
Další předkladatelMasarykova univerzita / Fakulta informatiky
Dodáno MŠMT v roce 2012Záznam s identifikačním kódem RIV/00216224:14330/11:00053105 v dodávce dat RIV12-MSM-14330___/01:1
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
Projekt1M0545 - Institut Teoretické Informatiky (2005-2011, MSM/1M)
Výzkumný záměrMSM0021620838 - Moderní metody, struktury a systémy informatiky (2005-2011, MSM)
Výzkumný záměrMSM0021622419 - Vysoce paralelní a distribuované výpočetní systémy (2005-2011, MSM)