| Identifikační kód |
RIV/00216224:14330/08:00024875 |
| Název v anglickém jazyce |
Finding branch-decomposition and rank-decomposition |
| Druh |
J - Recenzovaný odborný článek (Jimp, Jsc a Jost) |
| Poddruh |
- |
| Jazyk |
eng - angličtina |
| Obor - skupina |
I - Informatika |
| Obor |
IN - Informatika |
| Rok uplatnění |
2008 |
| 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 |
2 |
| Počet domácích tvůrců |
1 |
| Výčet všech uvedených jednotlivých tvůrců |
Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646)
Sang-il Oum (státní příslušnost: KR - Korejská republika) |
| Popis výsledku v anglickém jazyce |
We present a new algorithm that can output the rank-decomposition of width at most $k$ of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outputs its branch-decomposition of width atmost $k$ if such exists. This algorithm works also for partitioned matroids. Both these algorithms are fixed-parameter tractable, that is, they run in time $O(n^3)$ for each fixed value of $k$ where $n$ is the number of vertices / elements of the input. |
| Klíčová slova oddělená středníkem |
graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm |
| Stránka www, na které se nachází výsledek |
- |
| Odkaz na údaje z výzkumu |
- |