Algorithmic applications of linear rank-width

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GANIAN Robert

Rok publikování 2010
Druh Konferenční abstrakty
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.