---
title: "Graph Theoretical Characterization and Computation of Answer Sets"
authors:
  - "Thomas Linke"
doi: ""
url: "https://ijcai.org/proceedings/2001/89"
pdf: "https://ijcai.org/proceedings/2001/0089.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "641-647"
track: ""
keywords:
---

# Graph Theoretical Characterization and Computation of Answer Sets

Thomas Linke

*Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence*, pages 641-647.

## Abstract

We give a graph theoretical characterization of answer sets of normal logic programs. We show that there is a one-to-one correspondence between answer sets and a special, non-standard graph coloring of so-called block graphs of logic programs. This leads us to an alternative implementation paradigm to compute answer sets, by computing non-standard graph colorings. Our approach is rule-based and not atom-based like most of the currently known methods. We present an implementation for computing answer sets which works on polynomial space.