Home
Hasso-Plattner-Institut
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

schließen

schließen

schließen

schließen

schließen

schließen

schließen

schließen
  1. sand-iwoca

31.05.2024

Two Papers accepted at SAND and IWOCA

We have more good paper acceptance news! Together with researchers from the University of Liverpool, George Skretas wrote the paper All for one and one for all: An O(1)-Musketeers Universal Transformation for Rotating Robots. It will appear at the Symposium on Algorithmic Foundations of Dynamic Networks (SAND) on 5-7 June in Patras, Greece. The paper asks what the family of two-dimensional geometric shapes is that can be transformed into each other by a sequence of rotation operations, none of which disconnects the shape. The model represents programmable matter systems consisting of \(n\) devices lying on the cells of a two-dimensional square grid, interconnected modules that perform the minimal mechanical operation of 90 degree rotations around each other. The goal is to transform an initial shape of modules A into a target shape B. The authors prove that any pair of such shapes can be transformed into each other within an optimal \(O(n^2)\) rotation operations none of which disconnects the shape.

The second paper was written by Shaily Verma together with coauthors from the Institute of Mathematical Sciences in Chennai, the University of Bergen and the University of Groningen. Titled Parameterized Complexity of Paired Domination, it was accepted at the International Workshop on Combinatorial Algorithms (IWOCA) taking place on 1-3 July in Ischia, Italy. The Dominating Set problem generally models a guarding problem in which one needs to use the smallest number of guards to protect a certain object. Under this model, it is natural to desire an additional property: each guard has a partner with whom they back up each other. The corresponding problem is called Paired Dominating Set. In the paper, the authors study the parameterized complexity of the problem with respect to different graph parameters. The main result is an FPT algorithm for the problem parameterized by the treewidth of the graph with best running time guarantee.