1 citations · 4 across the 10 of their papers we have counts for
17 papers
Defensive Alliances in Signed Networks
Emmanuel Arrighi, Zhidan Feng, Henning Fernau +3
The analysis of (social) networks and multi-agent systems is a central theme in Artificial Intelligence. Some line of research deals with finding groups of agents that could work t…
Kernelizing Temporal Exploration Problems
Emmanuel Arrighi, Fedor V. Fomin, Petr Golovach +1
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs that s…
Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing
Sven Fiergolla, Kevin Goergen, Patrick Neises +1
The Kemeny Rank Aggregation (KRA) problem is a well-studied problem in the field of Social Choice with a variety of applications in many different areas like databases and search e…
All Paths Lead to Rome
Kevin Goergen, Henning Fernau, Esther Oest +1
All roads lead to Rome is the core idea of the puzzle game Roma. It is played on an grid consisting of quadratic cells. Those cells are grouped into boxes of at most f…
Learning from Positive and Negative Examples: New Proof for Binary Alphabets
Jonas Lingg, Mateus de Oliveira Oliveira, Petra Wolf
One of the most fundamental problems in computational learning theory is the the problem of learning a finite automaton consistent with a finite set of positive examples an…
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs
Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz +2
We study the computational complexity of determining structural properties of edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic b…
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann +4
In the Intersection Non-Emptiness problem, we are given a list of finite automata over a common alphabet as input, and the goal is to determine whether some…
Decomposing Permutation Automata
Ismaël Jecker, Nicolas Mazzocchi, Petra Wolf
A deterministic finite automaton (DFA) is composite if its language can be decomposed into an intersection of languages of smaller DFAs. Otherwise, A is prime. This notion of prima…
Diversity in Kemeny Rank Aggregation: A Parameterized Approach
Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov +2
In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of resea…
Properties of Graphs Specified by a Regular Language
Volker Diekert, Henning Fernau, Petra Wolf
Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property . What happens if this question is modified i…
A Timecop's Chase Around the Table
Nils Morawietz, Petra Wolf
We consider the cops and robber game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i.e., for each edge, a…
Improving Run Length Encoding by Preprocessing
Sven Fiergolla, Petra Wolf
The Run Length Encoding (RLE) compression method is a long standing simple lossless compression scheme which is easy to implement and achieves a good compression on input data whic…
Synchronizing Deterministic Push-Down Automata Can Be Really Hard
Henning Fernau, Petra Wolf, Tomoyuki Yamakami
The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend…
Synchronization of Deterministic Visibly Push-Down Automata
Henning Fernau, Petra Wolf
We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a s…
Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
Petra Wolf, Henning Fernau
The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton M as input, whether the language L(M) accepted by M contains any positive instance of the…
Synchronization under Dynamic Constraints
Petra Wolf
Imagine an assembly line where a box with a lid and liquid in it enters in some unknown orientation. The box should leave the line with the open lid facing upwards with the liquid…
From Decidability to Undecidability by Considering Regular Sets of Instances
Petra Wolf
We are lifting classical problems from single instances to regular sets of instances. The task of finding a positive instance of the combinatorial problem in a potentially infi…