1 citations · 1 across the 3 of their papers we have counts for
5 papers
On the Complexity of Fundamental Problems for DAG-Compressed Graphs
Florian Chudigiewitsch, Till Tantau, Felix Winkler
A DAG compression of a (typically dense) graph is a simple data structure that stores how vertex clusters are connected, where the clusters are described indirectly as sets of reac…
The Descriptive Complexity of Relation Modification Problems
Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz +2
A relation modification problem gets a logical structure and a natural number k as input and asks whether k modifications of the structure suffice to make it satisfy a predefined p…
On the Descriptive Complexity of Vertex Deletion Problems
Max Bannach, Florian Chudigiewitsch, Till Tantau
Vertex deletion problems for graphs are studied intensely in classical and parameterized complexity theory. They ask whether we can delete at most k vertices from an input graph su…
Existential Second-Order Logic Over Graphs: Parameterized Complexity
Max Bannach, Florian Chudigiewitsch, Till Tantau
By Fagin's Theorem, NP contains precisely those problems that can be described by formulas starting with an existential second-order quantifier, followed by only first-order quanti…
Computational Complexity of Deciding Provability in Linear Logic and its Fragments
Florian Chudigiewitsch
Linear logic was conceived in 1987 by Girard and, in contrast to classical logic, restricts the usage of the structural inference rules of weakening and contraction. With this, ato…