Finding branch-decomposition and rank-decomposition (Extended abstract)
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Article in Proceedings |
| Conference | European Symposium on Algorithms (ESA 2007) |
| MU Faculty or unit | |
| Citation | |
| Web | |
| 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: |