| Identifikační kód | RIV/00216224:14330/11:00065893 |
|---|
| Název v anglickém jazyce | Thread graphs, linear rank-width and their algorithmic applications |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2011 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 4 |
|---|
| Počet tvůrců celkem | 1 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Robert Ganian (státní příslušnost: US - Spojené státy americké, domácí tvůrce: A, vedidk: 6376290) |
|---|
| Popis výsledku v anglickém jazyce | Many 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á slova oddělená středníkem | rank-width; linear rank-width; thread graphs; bandwidth; path-width |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/978-3-642-19222-7_5 |
|---|