10 citations · 15 across the 22 of their papers we have counts for
5 papers · 1 filter
Computing Smallest Convex Intersecting Polygons
Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak +1
A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of comput…
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
Esther Galby, Sandor Kisfaludi-Bak, Daniel Marx +1
In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgr…
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves in , it provides a ro…
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertice…
Computing list homomorphisms in geometric intersection graphs
Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…