About: Parameterized Complexity Results for Exact Bayesian Network Structure Learning

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Parameterized Complexity Results for Exact Bayesian Network Structure Learning Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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{\%22a}ckstr\%22{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. 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{\%22a}ckstr\%22{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. (en)
Title	Parameterized Complexity Results for Exact Bayesian Network Structure Learning Parameterized Complexity Results for Exact Bayesian Network Structure Learning (en)
skos:prefLabel	Parameterized Complexity Results for Exact Bayesian Network Structure Learning Parameterized Complexity Results for Exact Bayesian Network Structure Learning (en)
skos:notation	RIV/00216224:14330/13:00072814!RIV14-MSM-14330___
http://linked.open...avai/predkladatel	Fakulta informatiky
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(EE2.3.30.0009)
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Ordyniak, Sebastian
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	95323
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/13:00072814
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	probabilistic network structure learning; parameterized complexity; algorithms (en)
http://linked.open.../riv/klicoveSlovo	parameterized complexity probabilistic network structure learning algorithms
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[8276EE30EA4B]
http://linked.open...i/riv/nazevZdroje	JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
http://linked.open...in/vavai/riv/obor	BD
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Employment of Newly Graduated Doctors of Science for Scientific Excellence
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	46
http://linked.open...iv/tvurceVysledku	Ordyniak, Sebastian Szeider, Stefan
http://linked.open...ain/vavai/riv/wos	000315862100001
issn	1076-9757
number of pages	40 (xsd:int)
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software