Detailed Information on Publication Record
2013
Parameterized Complexity Results for Exact Bayesian Network Structure Learning
ORDYNIAK, Sebastian and Stefan SZEIDERBasic information
Original name
Parameterized Complexity Results for Exact Bayesian Network Structure Learning
Authors
ORDYNIAK, Sebastian (276 Germany, guarantor, belonging to the institution) and Stefan SZEIDER (40 Austria)
Edition
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, MARINA DEL REY, AI ACCESS FOUNDATION, 2013, 1076-9757
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10000 1. Natural Sciences
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
Impact factor
Impact factor: 0.904
RIV identification code
RIV/00216224:14330/13:00072814
Organization unit
Faculty of Informatics
UT WoS
000315862100001
Keywords in English
probabilistic network structure learning; parameterized complexity;algorithms
Tags
International impact, Reviewed
Změněno: 26/2/2018 09:08, RNDr. Pavel Šmerk, Ph.D.
Abstract
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.
Links
| EE2.3.30.0009, research and development project |
|