Talks and Poster Presentations (with Proceedings-Entry):
M. Abseher, B. Bliem, G. Charwat, F. Dusberger, S. Woltran:
"Computing Secure Sets in Graphs using Answer Set Programming.";
Talk: ASPOCP 2014 - 7th Workshop on Answer Set Programming and Other Computing Paradigms,
Wien;
07-23-2014; in: "7th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2014",
(2014).
English abstract:
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.
Keywords:
secure sets, security in graphs, alliances in graphs
Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_231409.pdf
Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen
Created from the Publication Database of the Vienna University of Technology.