| Identifikační kód | RIV/00216224:14330/11:00049978 |
|---|
| Název v anglickém jazyce | Clique-width: When Hard Does Not Mean Impossible |
|---|
| 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 | 2 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 3 |
|---|
| 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)
Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646)
Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099) |
|---|
| Popis výsledku v anglickém jazyce | In recent years, the parameterized complexity approach has lead to the introduction of many new algorithms and frameworks on graphs and digraphs of bounded clique-width and, equivalently, rank-width. However, despite intensive work on the subject, therestill exist well-established hard problems where neither a parameterized algorithm nor a theoretical obstacle to its existence are known. Our article is interested mainly in the digraph case, targeting the well-known Minimum Leaf Out-Branching (cf. alsoMinimum Leaf Spanning Tree) and Edge Disjoint Paths problems on digraphs of bounded clique-width with non-standard new approaches. |
|---|
| Klíčová slova oddělená středníkem | clique-width; parameterized algorithm; XP |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|