6 citations · 12 across the 18 of their papers we have counts for
7 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…
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the…
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…
Parameterized Algorithms for Upward Planarity
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-pa…
Longest Cycle above Erdős-Gallai Bound
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an algorithm that for k\geq 0 in ti…
Detours in Directed Graphs
Fedor V. Fomin, Petr A. Golovach, William Lochet +3
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Pa…