[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

M. Lackner, A. Pfandler:
"Fixed-Parameter Algorithms for Finding Minimal Models";
Vortrag: Principles of Knowledge Representation and Reasoning (KR), Rome, Italy; 10.06.2012 - 14.06.2012; in: "Proceedings of 13th int. conf. on Principles of Knowledge Representation and Reasoning", G. Brewka, T. Eiter, S. McIlraith (Hrg.); AAAI Press, (2012), ISBN: 978-1-57735-561-8; Paper-Nr. 4880, 11 S.



Kurzfassung englisch:
Computing minimal models is an important task in Knowledge Representation and Reasoning that appears in formalisms such as circumscription, diagnosis and answer set programming. Even the most basic question of whether there exists a minimal model containing a
given variable is known to be P 2 -complete. In this work we study the problem of computing minimal models from the viewpoint of parameterized complexity theory. We perform an extensive complexity
analysis of this problem with respect to eleven parameters.
Tractable fragments based on combinations of these parameters are identified by giving several fixedparameter algorithms. For the remaining combinations we show parameterized hardness results and thus prove that under usual complexity theoretic assumptions no
further fixed-parameter algorithms exist for these parameters.


Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.