2008
Finding branch-decomposition and rank-decomposition
HLINĚNÝ, Petr a Sang-il OUMZákladní údaje
Originální název
Finding branch-decomposition and rank-decomposition
Název česky
Výpočet branch- a rank-dekompozic
Autoři
HLINĚNÝ, Petr (203 Česká republika, garant) a Sang-il OUM (410 Korejská republika)
Vydání
SIAM Journal on Computing, USA, SIAM, 2008, 0097-5397
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 1.459
Kód RIV
RIV/00216224:14330/08:00024875
Organizační jednotka
Fakulta informatiky
UT WoS
000258895100012
Klíčová slova anglicky
graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 1. 6. 2009 13:05, prof. RNDr. Petr Hliněný, Ph.D.
V originále
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 at most $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.
Česky
Přinášíme nový algoritmus, který počítá optimální rank-dekompozici grafu, optimální branch-dekompozici matroidu nad konečným tělesem, v FPT čase n^3.
Návaznosti
| GA201/08/0308, projekt VaV |
| ||
| MSM0021622419, záměr |
|