Výpočet branch- a rank-dekompozic

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00024875" target="_blank" >RIV/00216224:14330/08:00024875 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Finding branch-decomposition and rank-decomposition
Popis výsledku v původní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.
Název v anglickém jazyce
Finding branch-decomposition and rank-decomposition
Popis výsledku anglicky
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.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—

Projekt
<a href="/cs/project/GA201%2F08%2F0308" target="_blank" >GA201/08/0308: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2008
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)