A Parametrized Algorithm for Matroid Branch-Width
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Computing |
| MU Faculty or unit | |
| Citation | |
| Web | http://epubs.siam.org/sam-bin/dbq/toc/SICOMP/35/2 |
| Field | Informatics |
| Keywords | representable matroid; parametrized algorithm; branch-width; rank-width |
| Description | 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. |
| Related projects: |