5 citations · 6 across the 22 of their papers we have counts for
18 papers · 1 filter
Maximum Satisfiability of Simple Temporal Problems
Johannes K. Fichte, Johanna Groven, Peter Jonsson +2
The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consist…
Representative Sets in Propositional Abduction
Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist +1
The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an…
Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
Victor Lagerkvist, Johanna Groven, Leif Eriksson
The region connection calculus () and Allen's interval algebra () are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n…
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to…
New Perspectives on Semiring Applications to Dynamic Programming
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
Semiring algebras have been shown to provide a suitable language to formalize many noteworthy combinatorial problems. For instance, the Shortest-Path problem can be seen as a speci…
Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
The -Coloring problem is a well-known generalization of the classical NP-complete problem -Coloring where the task is to determine whether an input graph admits a homomorphis…