"Algorithmic applications of linear rank-width"@en . . "Algorithmic applications of linear rank-width" . . "RIV/00216224:14330/10:00044285" . . "rank-width; parameterized algorithms"@en . "Ganian, Robert" . . . "14330" . "[16813C6B6912]" . . . "1"^^ . . . "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." . . "1"^^ . "P(GA201/08/0308), P(GC201/09/J021), S" . . "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."@en . "Algorithmic applications of linear rank-width"@en . . "Algorithmic applications of linear rank-width" . . . . "245925" . . "RIV/00216224:14330/10:00044285!RIV11-GA0-14330___" .