1 citations · 1 across the 9 of their papers we have counts for
10 papers
How Close is a Tree to a Euclidean Minimum Spanning Tree?
Todor Antić, Jiří Fiala, Jelena Glišić +8
Let be a straight-line crossing-free drawing of a tree . A \emph{bad pair} in is a pair of non-adjacent vertices of whose Euclidean distance in is smaller than t…
Modelling Network Resilience: The Complexity of Some Graph Division Games
Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Antonio Lauerbach +1
Motivated by the controller placement problems in software-defined networks and the fair division principles of classical "cake cutting", we investigate the following two-player ze…
The Parameterized Complexity of Coloring Mixed Graphs
Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper +1
A mixed graph contains (undirected) edges as well as (directed) arcs, thus generalizing undirected and directed graphs. A proper coloring of a mixed graph assigns a positiv…
Coloring and Recognizing Directed Interval Graphs
Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen +3
A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particul…
Exact and approximation algorithms for sensor placement against DDoS attacks
Konstanty Junosza-Szaniawski, Dariusz Nogalski, Paweł Rzążewski
In a DDoS attack (Distributed Denial of Service), an attacker gains control of many network users through a virus. Then the controlled users send many requests to a victim, leading…
Online coloring of disk graphs
Joanna Chybowska-Sokół, Konstanty Junosza-Szaniawski
In this paper, we give a family of online algorithms for the classical coloring problem of intersection graphs of discs with bounded diameter. Our algorithms make use of a geometri…