D 2007

Finding branch-decomposition and rank-decomposition (Extended abstract)

HLINĚNÝ, Petr a Sang-il OUM

Základní údaje

Originální název

Finding branch-decomposition and rank-decomposition (Extended abstract)

Název česky

Výpočet branch- a rank-dekompozic

Autoři

HLINĚNÝ, Petr ORCID a Sang-il OUM

Vydání

Berlin, European Symposium on Algorithms (ESA 2007), s. 163-174, 2007

Nakladatel

Springer Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Kód RIV

RIV/00216224:14330/07:00022470

Organizační jednotka

Fakulta informatiky

ISBN

978-3-540-75519-7

UT WoS

000252040000015

Klíčová slova anglicky

graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 12. 6. 2008 10:51, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

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

MSM0021622419, záměr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy