3 papers
cs.CC2026
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…
cs.CC2026
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…
cs.AI2025
Structure-Aware Encodings of Argumentation Properties for Clique-width
Yasir Mahmood, Markus Hecher, Johanna Groven +1
Structural measures of graphs, such as treewidth, are central tools in computational complexity resulting in efficient algorithms when exploiting the parameter. It is even known th…