9 citations · 18 across the 14 of their papers we have counts for
15 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…
Coloring distance graphs on the plane
Joanna Chybowska-Sokół, Konstanty Junosza-Szaniawski, Krzysztof Węsek
We consider the coloring of certain distance graphs on the Euclidean plane. Namely, we ask for the minimal number of colors needed to color all points of the plane in such a way th…
Online Coloring of Short Intervals
Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski +2
We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in . For it is the class of unit interval graphs, and for $σ…
Fixing improper colorings of graphs
Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff +2
In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper -coloring of a graph . We investigate the problem of f…
First non-trivial upper bound on the circular chromatic number of the plane
Konstanty Junosza-Szaniawski
We consider circular version of the famous Nelson-Hadwiger problem. It is know that 4 colors are necessary and 7 colors suffice to color the euclidean plane in such a way that poin…
Fractional and -fold colouring of the plane
Jarosław Grytczuk, Konstanty Junosza-Szaniawski, Joanna Sokół +1
We present results referring to the Hadwiger-Nelson problem which asks for the minimum number of colours needed to colour the plane with no two points at distance having the sa…
Counting independent sets via Divide Measure and Conquer method
Konstanty Junosza-Szaniawski, Michal Tuczynski
In this paper we give an algorithm for counting the number of all independent sets in a given graph which works in time for subcubic graphs and in time $O^*(1.2369^…
Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer +5
We study the {\sc Clique} problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-set intersection graphs and straig…
An Exact Algorithm for the Generalized List -Coloring Problem
Konstanty Junosza-Szaniawski, Paweł Rzążewski
The generalized list -coloring is a common generalization of many graph coloring models, including classical coloring, -labeling, channel assignment and -coloring. Ev…
Determining L(2,1)-Span in Polynomial Space
Konstanty Junosza-Szaniawski, Paweł Rzą\zewski
A -L(2,1)-labeling of a graph is a function from its vertex set into the set , such that the labels assigned to adjacent vertices differ by at least 2, and labels a…