4 citations · 11 across the 15 of their papers we have counts for
9 papers · 1 filter
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…
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…
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…
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…
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…
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…
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…
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…