J 2013

Parameterized Complexity Results for Exact Bayesian Network Structure Learning

ORDYNIAK, Sebastian a Stefan SZEIDER

Základní údaje

Originální název

Parameterized Complexity Results for Exact Bayesian Network Structure Learning

Autoři

ORDYNIAK, Sebastian (276 Německo, garant, domácí) a Stefan SZEIDER (40 Rakousko)

Vydání

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, MARINA DEL REY, AI ACCESS FOUNDATION, 2013, 1076-9757

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10000 1. Natural Sciences

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.904

Kód RIV

RIV/00216224:14330/13:00072814

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000315862100001

Klíčová slova anglicky

probabilistic network structure learning; parameterized complexity;algorithms

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 26. 2. 2018 09:08, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter ``length of the solution plan.'' We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by B{\"a}ckstr\"{o}m and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which don't.

Návaznosti

EE2.3.30.0009, projekt VaV
Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci