1 citations · 1 across the 7 of their papers we have counts for
9 papers
A Fixed-Parameter Algorithm for Extending Upward Planar Drawings
Vera Chekan, Robert Ganian, Viktoriia Korchemna
An upward planar drawing of a directed acyclic graph is a planar drawing where every edge is pointed upward from its tail to head. Upward planar drawings are among the most natural…
The Complexity of Bayesian Network Learning: Revisiting the Superstructure
Robert Ganian, Viktoriia Korchemna
We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely…
Efficient Approximation of Fractional Hypertree Width
Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh +2
We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input -vertex -edge hypergraph of…
A Structural Complexity Analysis of Synchronous Dynamical Systems
Eduard Eiben, Robert Ganian, Thekla Hamm +1
Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product…
Counting Vanishing Matrix-Vector Products
Cornelius Brand, Viktoriia Korchemna, Michael Skotnica +1
Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let…
The Complexity of Fair Division of Indivisible Items with Externalities
Argyrios Deligkas, Eduard Eiben, Viktoriia Korchemna +1
We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent g…
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian, Thekla Hamm, Viktoriia Korchemna +2
The generic homomorphism problem, which asks whether an input graph admits a homomorphism into a fixed target graph , has been widely studied in the literature. In this arti…
Slim Tree-Cut Width
Robert Ganian, Viktoriia Korchemna
Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural propertie…
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
Cornelius Brand, Esra Ceylan, Christian Hatschka +2
Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by tre…