Algorithmic applications of linear rank-width
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F10%3A00044285" target="_blank" >RIV/00216224:14330/10:00044285 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Algorithmic applications of linear rank-width
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Algorithmic applications of linear rank-width
Popis výsledku anglicky
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.
Klasifikace
Druh
O - Ostatní výsledky
CEP obor
BD - Teorie informace
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2010
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů