Publication details

Algorithmic applications of linear rank-width

Authors

GANIAN Robert

Year of publication 2010
Type Conference abstract
MU Faculty or unit

Faculty of Informatics

Citation
Description Many NP-hard graph problems can be efficiently solved on graphs of bounded tree-width. Several articles have recently shown that the so-called rank-width parameter also allows efficient solution of most of these NP-hard problems, while being less restrictive than tree-width. On the other hand however, there exist problems of practical importance which remain hard not only on graphs of bounded rank-width, but even of bounded tree-width or trees. We will introduce linear rank-width, a width parameter which is obtained from rank-width by a restriction analogous to the one used on tree-width to obtain path-width, and show that on the class of graphs of linear rank-width 1 it is possible to solve problems which are hard even on trees.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info