Finding Branch-decompositions and Rank-decompositions

Warning

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

HLINĚNÝ Petr OUM Sang il

Year of publication 2007
Type Conference abstract
MU Faculty or unit

Faculty of Informatics

Citation
Description 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.
Related projects:

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