4 citations · 11 across the 15 of their papers we have counts for
20 papers
A Simple Algorithm for Counting Solutions to Integer Programs
Daniel Dadush, Anita Dürr, Thekla Hamm +2
We consider the problem of counting solutions to integer linear programming problems of the form where $A \in \{-Δ,\ldots,Δ\}^{m \times n…
Parameterized Complexity of Power Network Design: Coordinating Cable Placement is Hard
Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei
We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal ver…
A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
Sergio Cabello, Alexander Dobler, Gašper Fijavž +2
A drawing of a graph is 1-planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a 1-planar drawing belongs to o…
Computing crossing numbers with topological and geometric restrictions
Thekla Hamm, Fabian Klute, Irene Parada
Computing the crossing number of a graph is one of the most classical problems in computational geometry. Both it and numerous variations of the problem have been studied, and over…
A Structural Complexity Analysis of Synchronous Dynamical Systems
Eduard Eiben, Robert Ganian, Thekla Hamm +1
Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product…
Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian, Thekla Hamm, Dušan Knop +3
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function that t…
The Complexity of Envy-Free Graph Cutting
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspon…
Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian, Thekla Hamm, Dušan Knop +3
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that too…
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
Parinya Chalermsook, Fedor Fomin, Thekla Hamm +3
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation…
Approximate Evaluation of Quantitative Second Order Queries
Jan Dreier, Robert Ganian, Thekla Hamm
Courcelle's theorem and its adaptations to cliquewidth have shaped the field of exact parameterized algorithms and are widely considered the archetype of algorithmic meta-theorems.…
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…
The Complexity of Temporal Vertex Cover in Small-Degree Graphs
Thekla Hamm, Nina Klobas, George B. Mertzios +1
Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems TEMPORAL VERTEX COVER (or TVC) and SLIDING-WINDOW TEMPORAL VERTEX COVER(o…
Parameterised Partially-Predrawn Crossing Number
Thekla Hamm, Petr Hliněný
Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph param…
Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Robert Ganian, Thekla Hamm, Dušan Knop +2
Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly target…
A Unifying Framework for Characterizing and Computing Width Measures
Eduard Eiben, Robert Ganian, Thekla Hamm +2
Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specifi…
Crossing-Optimal Extension of Simple Drawings
Robert Ganian, Thekla Hamm, Fabian Klute +2
In extension problems of partial graph drawings one is given an incomplete drawing of an input graph and is asked to complete the drawing while maintaining certain properties.…
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
Eduard Eiben, Robert Ganian, Thekla Hamm +2
The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph , a conne…
Extending Partial 1-Planar Drawings
Eduard Eiben, Robert Ganian, Thekla Hamm +2
Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph…
Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
Jiehua Chen, Robert Ganian, Thekla Hamm
We investigate the following many-to-one stable matching problem with diversity constraints (SMTI-Diverse): Given a set of students and a set of colleges which have preferences ove…
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Eduard Eiben, Robert Ganian, Thekla Hamm +1
We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess ot…