Rank-width

This article does not cite any sources. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (November 2021) (Learn how and when to remove this template message)

Rank-width is a graph width parameter used in graph theory and parameterized complexity. This parameter indicates the minimum integer k for a given graph G so that the tree can be decomposed into tree-like structures by splitting its vertices such that each cut induces a matrix of rank at most k. Even though there are various other width parameters that have been shown to be very useful, but some of them like treewidth (or clique-width) are bounded for only for sparse (or dense) graphs. For the dense graphs, where clique-width can be used, there is no efficient algorithm deciding this parameter. This is where rank-width comes to the picture. There exists an algorithm running in polynomial time that decides if the rank-width of an input graph is at most k.

The best known relationship between rank-width and clique-width is as follows: ${\displaystyle k\leq c\leq 2^{k+1}-1}$, where c is the clique-width.

This mathematics-related article is a stub. You can help Wikipedia by .

• v
• t