Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Abseher, B. Bliem, G. Charwat, F. Dusberger, S. Woltran:
"Computing Secure Sets in Graphs using Answer Set Programming.";
Vortrag: ASPOCP 2014 - 7th Workshop on Answer Set Programming and Other Computing Paradigms,
Wien;
23.07.2014; in: "7th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2014",
(2014).
Kurzfassung englisch:
Problems from the area of graph theory always served as fruitful benchmarks in order to explore the performance of Answer Set
Programming (ASP) systems. A relatively new branch in graph theory is
concerned with so-called secure sets. It is known that verifying whether a set is secure in a graph is already co-NP-hard. The problem of enumerating all secure sets thus is challenging for ASP and its systems. In particular, encodings for this problem seem to require disjunction and also recursive aggregates. In this paper, we provide such encodings and analyze their performance using the Clingo system.
Schlagworte:
secure sets, security in graphs, alliances in graphs
Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_231409.pdf
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.