Publications in Scientific Journals:

F. Dusberger, M. Abseher, B. Bliem, G. Charwat, S. Woltran:
"Computing Secure Sets in Graphs using Answer Set Programming";
Journal of Logic and Computation, 2015 special issue (2015), 2015 special issue; 1 - 26.

English abstract:
The notion of secure sets is a rather new concept in the area of graph theory. Applied to social network analysis, the goal is to identify groups of entities that can repel any attack or influence from the outside. In this article, we tackle this problem by utilizing Answer Set Programming (ASP). It is known that verifying whether a set is secure in a graph is already co-NP-hard. Therefore, the problem of enumerating all secure sets is challenging for ASP and its systems. In particular, encodings for this problem seem to require disjunction and also recursive aggregates. Here, we provide such encodings and analyse their performance using the Clingo system. Furthermore, we study several problem variants, including multiple secure or insecure sets, and weighted graphs.

secure sets, graphs, answer set, computing

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.