Computing rank-width exactly

Abstract

We prove that the rank-width of an n-vertex graph can be computed exactly in time O(2(n)n(3) log(2) n log log n). To improve over a trivial O(3(n) log n)-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. (C) 2009 Elsevier B.V. All rights reserved.