Jonathan Dransfeld

dblp:416/6932 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2026
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2026 Engineering Dominating Patterns: A Fine-grained Case Study
abstract
The Dominating \(H\)-Pattern problem generalizes the classical \(k\)-Dominating Set problem: for a fixed pattern \(H\) and a given graph \(G\), the goal is to find an induced subgraph \(S\) of \(G\) such that (1) \(S\) is isomorphic to \(H\), and (2) \(S\) forms a dominating set in \(G\). Fine-grained complexity results show that on worstcase inputs, any significant improvement over the naive brute-force algorithm is unlikely, as this would refute the Strong Exponential Time Hypothesis. Nevertheless, a recent work by Dransfeld et al. (ESA 2025) reveals some significant improvement potential particularly in sparse graphs.
Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic, Marcus Wunderlich
ALENEX1
2025 Fine-Grained Classification of Detecting Dominating Patterns
Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic
ESA1