Algorithmic applications of linear rank-width
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Konferenční abstrakty |
| Fakulta / Pracoviště MU | |
| 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: |