Informace o publikaci
A Parametrized Algorithm for Matroid Branch-Width
| Název česky | Parametrizovaný algoritmus pro branch-width matroidů |
|---|---|
| Autoři | |
| Rok publikování | 2005 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Computing |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://epubs.siam.org/sam-bin/dbq/toc/SICOMP/35/2 |
| Obor | Informatika |
| Klíčová slova | representable matroid; parametrized algorithm; branch-width; rank-width |
| Popis | 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. |
| Související projekty: |