Computing Grounded Extensions Of Abstract Argumentation Frameworks. (28th November 2019)

• Record Type: Journal Article
• Authors: Nofal, Samer; Atkinson, Katie; Dunne, Paul E
• Is Part Of: Computer journal. Volume 64:Number 1(2021)
• Page Start: 54
• Page End: 63
• Publication Date: 2019-11-28
• Subjects: directed graph -- algorithm -- grounded extension -- argumentation graph -- argumentation semantics -- abstract argumentation framework; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz138
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: An abstract argumentation framework is a directed graph $(V, E)$ such that the vertices of $V$ denote abstract arguments and $E \subseteq V \times V$ represents the attack relation between them. We present a new ad hoc algorithm for computing the grounded extension of an abstract argumentation framework. We show that the new algorithm runs in $\mathcal{O}(|V|+|E|)$ time. In contrast, the existing state-of-the-art algorithm runs in $\mathcal{O}(|V|+|S||E|)$ time where $S$ is the grounded extension of the input graph.