with: Karl Bringmann • Marvin Künnemann • Dániel Marx • André Nusser
Accepted to SoCG 2022. (2022)
Recent
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Towards sub-quadratic diameter computation in geometric intersection graphs
with: Karl Bringmann • Marvin Künnemann • André Nusser • Zahra Parsaeian
Accepted to SoCG 2022. (2022)
Computing list homomorphisms in geometric intersection graphs
with: Karolina Okrasa • Paweł Rzążewski
(2022)
Journals
Online search for a hyperplane in high-dimensional Euclidean space
with: Antonios Antoniadis • Ruben Hoeksma • Kevin Schewior
Information Processing Letters 177: 106262 (2022)
Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals
on Few Faces
with: Jesper Nederlof • Erik Jan van Leeuwen
ACM Transactions on Algorithms 16(3), p 28:1–28:30 (2020)
The Homogeneous Broadcast Problem in Narrow and Wide Strips I:
Algorithms
with: Mark de Berg • Hans L. Bodlaender
Algorithmica 81(7), p 2934–2962 (2019)
The Homogeneous Broadcast Problem in Narrow and Wide Strips II:
Lower Bounds
with: Mark de Berg • Hans L. Bodlaender
Algorithmica 81(7), p 2963–2990 (2019)
The complexity of Dominating Set in geometric intersection
graphs
with: Mark de Berg • Gerhard J. Woeginger
Theoretical Computer Science 769, p 18–31 (2019)
On the number of touching pairs in a set of planar curves
with: Péter Györgyi • Bálint Hujter
Computational Geometry: Theory and Applications 67, p 29–37 (2018)
Conferences
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
with: Jesper Nederlof • Karol Węgrzycki
Proceedings of FOCS 2021. (2022)
Clique-Based Separators for Geometric Intersection Graphs
with: Mark de Berg • Morteza Monemizadeh • Leonidas Theocharous
32nd International Symposium on Algorithms and Computation, (ISAAC)
2021 Fukuoka, JP
A quasi-polynomial algorithm for well-spaced hyperbolic TSP
36th International Symposium on Computational Geometry (SoCG)
2020 Zurich, CH
Euclidean TSP in Narrow Strips
with: Henk Alkema • Mark de Berg
36th International Symposium on Computational Geometry (SoCG)
2020 Zurich, CH
Hyperbolic intersection graphs and (quasi)-polynomial time
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
2020 Salt Lake City, US
On One-Round Discrete Voronoi Games
with: Mark de Berg • Mehran Mehr
30th International Symposium on Algorithms and Computation, (ISAAC)
2019 Shanghai, CN
How Does Object Fatness Impact the Complexity of Packing in d
Dimensions?
with: Dániel Marx • Tom van der Zanden
30th International Symposium on Algorithms and Computation, (ISAAC)
2019 Shanghai, CN
On Geometric Set Cover for Orthants
with: Karl Bringmann • Michał Pilipczuk • Erik Jan van Leeuwen
27th Annual European Symposium on Algorithms, (ESA)
2019 Munich/Garching, DE
Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals
on Few Faces
with: Jesper Nederlof • Erik Jan van Leeuwen
30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
2019 San Diego, CA, US
An ETH-Tight Exact Algorithm for Euclidean TSP
with: Mark de Berg • Hans L. Bodlaender • Sudeshna Kolay
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS)
2018 Paris, FR
A framework for ETH-tight algorithms and lower bounds in geometric
intersection graphs
with: Mark de Berg • Hans L. Bodlaender • Dániel Marx • Tom C. van der Zanden
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC)
2018 Los Angeles, CA, US
The Dominating Set Problem in Geometric Intersection Graphs
with: Mark de Berg • Gerhard J. Woeginger
International Symposium on Parameterized and Exact Computation (IPEC)
2017 Vienna, AT
The Homogeneous Broadcast Problem in Narrow and Wide Strips
with: Mark de Berg • Hans L. Bodlaender
Workshop on Algorithms and Data Structures (WADS)
2017 St. John's, CA
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in
Disk Graphs
with: Tom C. van der Zanden
International Conference on Algorithms and Complexity (CIAC)
2017 Athens, GR
Connected Dominating Set on Unit Disk Graphs is W[1]-hard
with: Mark de Berg • Hans L. Bodlaender
European Workshop on Computational Geometry (EuroCG)
2016 Lugano, CH
Succinct tree coding for greedy navigation
with: Zoltán Király
9th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
2015 Fukuoka, JP
Notes on dual-critical graphs
with: Zoltán Király
8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
2013 Veszprém, HU
Book chapters
Lower Bounds for Dominating Set in Ball Graphs and for Weighted
Dominating Set in Unit-Ball Graphs
with: Mark de Berg
Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L.
Bodlaender on the Occasion of His 60th Birthday
In: Fomin F., Kratsch S., van Leeuwen E. (eds) Treewidth, Kernels,
and Algorithms. Lecture Notes in Computer Science, vol 12160.
Springer, Cham., p 31–48
Theses
ETH-tight algorithms for geometric network problems
advisors: Mark de Berg • Hans L. Bodlaender
TU Eindhoven, Department of Mathematics and Computer Science
2019
recipient.Preprints and Technical Reports
Dual-Critical Graphs: Notes on parity constrained orientations
EGRES Technical Report 2012-07
with: Zoltán Király
2012