A Parametrized Algorithm for Matroid Branch-Width

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr

Year of publication 2005
Type Article in Periodical
Magazine / Source SIAM Journal on Computing
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.