Finding branch-decomposition and rank-decomposition

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	2008
Type	Article in Periodical
Magazine / Source	SIAM Journal on Computing
MU Faculty or unit	Faculty of Informatics
Citation
Web	doi
Field	Informatics
Keywords	graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm
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(n^3)$ for each fixed value of $k$ where $n$ is the number of vertices / elements of the input.
Related projects:	Highly Parallel and Distributed Computing Systems Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity