Computability of Width of Submodular Partition Functions

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F09%3A10031828" target="_blank" >RIV/00216208:11320/09:10031828 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Computability of Width of Submodular Partition Functions
Popis výsledku v původním jazyce
The notion of submodular partition functions generalizes many of well-known tree decompositions of graphs. For fixed k, there are polynomial-time algorithms to determine whether a graph has tree-width, branch-width, etc. at most k. Contrary to these results, we show that there is no sub-exponential algorithm for determining whether the width of a given submodular partition function is at most two. In addition, we also develop another dual notion for submodular partition functions which is analogous to loose tangles for connectivity functions.
Název v anglickém jazyce
Computability of Width of Submodular Partition Functions
Popis výsledku anglicky
The notion of submodular partition functions generalizes many of well-known tree decompositions of graphs. For fixed k, there are polynomial-time algorithms to determine whether a graph has tree-width, branch-width, etc. at most k. Contrary to these results, we show that there is no sub-exponential algorithm for determining whether the width of a given submodular partition function is at most two. In addition, we also develop another dual notion for submodular partition functions which is analogous to loose tangles for connectivity functions.

Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2009
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ů

Podobné výsledky(10)