A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond

DOI10.1613/jair.3968zbMath1269.68055arXiv1402.0588OpenAlexW3103381521WikidataQ129489519 ScholiaQ129489519MaRDI QIDQ2842195

Christer Bäckström, Peter Jonsson

Publication date: 13 August 2013

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0588

zbMATH Keywords

computational complexityNP-hardplanningcausal graphsSP-closed graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Limitations of acyclic causal graphs for planning ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Backdoors to planning