Finding Branch-decompositions and Rank-decompositions

HLINĚNÝ, Petr a Sang il OUM. Finding Branch-decompositions and Rank-decompositions. In Joint Meeting of the AMS - NZMS 2007. 2007.

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 (203 Česká republika, garant) a Sang il OUM (410 Korejská republika).
• Vydání: Joint Meeting of the AMS - NZMS 2007, 2007.

Další údaje

• Originální 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í
• WWW: conference
• 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: branch-width, matroid, parametrized algorithm
• Příznaky: Mezinárodní význam

Anotace

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.

Anotace č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