a 2007

Finding Branch-decompositions and Rank-decompositions

HLINĚNÝ, Petr a Sang il OUM

Základní údaje

Originální název

Finding Branch-decompositions and Rank-decompositions

Název česky

Nalezení rankové a větvené dekompozice

Autoři

HLINĚNÝ, Petr ORCID a Sang il OUM

Vydání

Joint Meeting of the AMS - NZMS 2007, 2007

Další údaje

Jazyk

angličtina

Typ výsledku

Konferenční abstrakt

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nový Zéland

Utajení

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

Odkazy

Kód RIV

RIV/00216224:14330/07:00024655

Organizační jednotka

Fakulta informatiky

UT WoS

000252040000015

Klíčová slova anglicky

matroid; branch-width; parametrized algorithm

Štítky

Příznaky

Mezinárodní význam
Změněno: 27. 6. 2008 11:16, Ing. Dana Komárková

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(n3) for each fixed value of k where n is the number of vertices / elements of the input.

Česky

Prezentujeme nový algoritmus, který v kubickém parametrizovaném čase nalezne optimální rankovou dekompozici daného grafu omezené rank-width.

Návaznosti

GA201/05/0050, projekt VaV
Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky