| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428104 | Information Processing Letters | 2009 | 4 Pages |
Abstract
We prove that the rank-width of an n-vertex graph can be computed exactly in time O(n2n3log2nloglogn). To improve over a trivial O(n3logn)-time algorithm, we develop a general framework for decompositions on which an optimal decomposition can be computed efficiently. This framework may be used for other width parameters, including the branch-width of matroids and the carving-width of graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
