RIV/00216224:14330/11:00049676 - Thread graphs, linear rank-width and their algorithmic applications (2011)

Údaje o výsledku
Identifikační kódRIV/00216224:14330/11:00049676
Název v původním jazyceThread graphs, linear rank-width and their algorithmic applications
DruhD - Článek ve sborníku
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ýsledku4
Ú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íD - Článek ve sborníku
Skupina oboru v hodnocení04 - Technické a informatické vědy
Konkrétní způsob(y) hodnocení výsledkuČlánek ve sborníku evidovaném v databázi Scopus bodovaný podle SJR zdroje typu Book Series nebo Conference Proceedings
Bodové ohodnocení53,461
Faktor korekce100,9 %
Body (upravené podle přílohy č. 8 Metodiky)53,957
Rozdělení výsledku mezi předkladatele
OrganizaceVýzkumná organizace?PodílBodyBody (upravené podle přílohy č. 8 Metodiky)
Masarykova univerzita / Fakulta informatikyano100,0 %53,46153,957
Tvůrci výsledku
Počet tvůrců celkem1
Počet domácích tvůrců1
TvůrceGanian Robert (státní příslušnost: US - Spojené státy americké; A - domácí tvůrce; G - garant výsledku; vedidk: 6376290)
Údaje blíže specifikující výsledek
Popis v původním jazyceMany NP-hard graph problems can be efficiently solved on graphs of bounded tree-width. Several articles have recently shown that the so-called rank-width parameter also allows efficient solution of most of these NP-hard problems, while being less restrictive than tree-width. On the other hand however, there exist problems of practical importance which remain hard on graphs of bounded rank-width, and even of bounded tree-width or trees. In this paper we consider a more restrictive version of rank-width called linear rank-width, analogously to how path-width is obtained from tree-width. We first provide a characterization of graphs of linear rank-width 1 and then show that on such graphs it is possible to obtain better algorithmic results than on distance hereditary graphs and even trees. Specifically, we provide polynomial algorithms for computing path-width, dominating bandwidth and a 2-approximation of ordinary bandwidth on graphs of linear rank-width 1.
Klíčová slovarank-width; linear rank-width; thread graphs; bandwidth; path-width
Kód UT ISI000290418700005
Název sborníkuCombinatorial Algorithms 2010
Rozsah stran38-42
ISBN978-3-642-19221-0
Počet stran výsledku5
Název nakladateleSpringer-Verlag
Místo vydáníLondýn, Velká Británie
Místo konání akceLondýn, Velká Británie
Rok konání akce2010
Typ akce podle státní příslušnoti účastníkůWRD - Světová
Údaje o tomto záznamu o výsledku
PředkladatelMasarykova univerzita / Fakulta informatiky
DodavatelGA0 - Grantová agentura České republiky (GA ČR)
Rok sběru2012
Systémové označení dodávky datRIV12-GA0-14330___/02:1
SpecifikaceRIV/00216224:14330/11:00049676!RIV12-GA0-14330___
Kontrolní kód[1CF1F27ECF6F]
Další výskyty tohoto výsledku od stejného předkladatele
Dodáno GA ČR v roce 2014Záznam s identifikačním kódem RIV/00216224:14330/11:00065893 v dodávce dat RIV14-GA0-14330___/01:1
Dodáno MŠMT v roce 2012Záznam s identifikačním kódem RIV/00216224:14330/11:00049676 v dodávce dat RIV12-MSM-14330___/01:1
Dodáno MŠMT v roce 2014Záznam s identifikačním kódem RIV/00216224:14330/11:00065893 v dodávce dat RIV14-MSM-14330___/01:1
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
ProjektGC201/09/J021 - Strukturální teorie grafů a parametrizovaná složitost (2009-2010, GA0/GC)
Projekt1M0545 - Institut Teoretické Informatiky (2005-2011, MSM/1M)
Výzkumný záměrMSM0021622419 - Vysoce paralelní a distribuované výpočetní systémy (2005-2011, MSM)
S - Specifický výzkum na vysokých školách