A Parametrized Algorithm for Matroid Branch-Width

HLINĚNÝ, Petr. A Parametrized Algorithm for Matroid Branch-Width. SIAM Journal on Computing. USA: SIAM, 2005, roč. 35, č. 2, s. 259 - 277. ISSN 0097-5397.

Základní údaje

Originální název

A Parametrized Algorithm for Matroid Branch-Width

Název česky

Parametrizovaný algoritmus pro branch-width matroidů

Autoři

HLINĚNÝ, Petr ORCID

Vydání

SIAM Journal on Computing, USA, SIAM, 2005, 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

URL

Impakt faktor

Impact factor: 1.195

Kód RIV

RIV/00216224:14330/05:00012752

Organizační jednotka

Fakulta informatiky

UT WoS

000233930200001

Klíčová slova anglicky

representable matroid; parametrized algorithm; branch-width; rank-width

Štítky

branch-width, parametrized algorithm, rank-width, representable matroid

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Branch-width is a structural parameter very closely related to tree-width, but branchwidth has an immediate generalization from graphs to matroids. We present an algorithm that, for a given matroid M of bounded branch-width t which is represented over a finite field, finds a branch decomposition of M of width at most 3t in cubic time. Then we show that the branch-width of M is a uniformly fixed-parameter tractable problem. Other applications include recognition of matroid properties definable in the monadic second-order logic for bounded branch-width, or [Oum] a cubic time approximation algorithm for graph rank-width and clique-width.

Česky

Branch-width je strukturální parametr blízký známé tree-width, avšak mající okamžité zobecnění na matroidy. Zde uvedeme algoritmus, který pro daný matroid M s omezenou branch-width ta reprezentovaný nad konečným tělesem najde dekompozici šířky nejvýše 3t v kubickém čase. Tak dokážeme, že branch-width je uniformně FPT problém. Další aplikace zahrnují rozpoznávání matroidových vlastností v monadické logice druhého řádu pro omezenou branch-width, nebo [Oum] kubický aproximační algoritmus pro grafovou rank-width a clique-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