24 citations · 124 across the 75 of their papers we have counts for
9 papers · 1 filter
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…
Testing Upward Planarity of Partial -Trees
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We present an -time algorithm to test whether an -vertex directed partial -tree is upward planar. This result improves upon the previously best known algorithm, which…
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…
Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokrývka, André Schidler +2
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar resul…
Bounding and computing obstacle numbers of graphs
Martin Balko, Steven Chaplick, Robert Ganian +4
An obstacle representation of a graph consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of to points such that…
Algorithmic Applications of Tree-Cut Width
Robert Ganian, Eun Jung Kim, Stefan Szeider
The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper,…