On finding optimal polytrees (2015)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/15:00087407 |
|---|---|
| Název v anglickém jazyce | On finding optimal polytrees |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2015 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 1 |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 1 |
| Výčet všech uvedených jednotlivých tvůrců | Serge Gaspers (státní příslušnost: AU - Austrálie) Mikko Koivisto (státní příslušnost: FI - Finská republika) Mathieu Liedloff (státní příslušnost: FR - Francouzská republika) Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A) Stefan Szeider (státní příslušnost: AT - Rakouská republika) |
| Popis výsledku v anglickém jazyce | We study the NP-hard problem of finding a directed acyclic graph (DAG) on a given set of nodes so as to maximize a given scoring function. The problem models the task of inferring a probabilistic network from data, which has been studied extensively in the fields of artificial intelligence and machine learning. Several variants of the problem, where the output DAG is constrained in several ways, are NP-hard as well, for example when the DAG is required to have bounded in-degree, or when it is required to be a polytree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. In this paper, we generalize this polynomial-time result to polytrees that can be turned into a branching by deleting a constant number of arcs. Our algorithm stems from a matroid intersection formulation. |
| Klíčová slova oddělená středníkem | Directed acyclic graphs; Branchings; Polytrees; Parameterized complexity; Matroids; Probabilistic networks |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1016/j.tcs.2015.05.012 |
Údaje o výsledku v závislosti na druhu výsledku
| Název periodika | Theoretical Computer Science |
|---|---|
| ISSN | 0304-3975 |
| Svazek periodika | 592 |
| Číslo periodika v rámci uvedeného svazku | 1 |
| Stát vydavatele periodika | US - Spojené státy americké |
| Počet stran výsledku | 10 |
| Strana od-do | 49-58 |
| Kód UT WoS článku podle Web of Science | 000358624300005 |
| EID výsledku v databázi Scopus | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2016 |
| Specifikace | RIV/00216224:14330/15:00087407!RIV16-MSM-14330___ |
| Datum poslední aktualizace výsledku | 24.05.2016 |
| Kontrolní číslo | 191637341 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný MŠMT v programu EE | EE2.3.30.0009 - Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci (2012 - 2015) |
|---|