Publication details
Finding branch
-decomposition and rank-decomposition
| Basic information | |
|---|---|
| Original title: | Finding branch-decomposition and rank-decomposition |
| Authors: | Petr Hliněný, Sang-il Oum |
| Further information | |
|---|---|
| Citation: | HLINĚNÝ, Petr - OUM, Sang-il. Finding branch-decomposition and rank-decomposition. SIAM Journal on Computing, USA, SIAM, USA. ISSN 0097-5397, 2008, vol. 38, no. 3, pp. 1012-1032. |
| Original language: | English |
| Field: | Informatika |
| WWW: |  doi |
| Type: | Article in Periodical |
| Keywords: | graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm |
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
