Miloš Stojaković
YOU?
Author Swipe
View article: Maker playing against an invisible Breaker
Maker playing against an invisible Breaker Open
We initiate the study of the phantom version of Maker-Breaker positional games. In a phantom game, the moves of one of the players are hidden from the other player, who still has the complete information. We look at the biased $(a:b)$ Make…
View article: Polychromatic Coloring of Tuples in Hypergraphs
Polychromatic Coloring of Tuples in Hypergraphs Open
A hypergraph $H$ consists of a set $V$ of vertices and a set $E$ of hyperedges that are subsets of $V$. A $t$-tuple of $H$ is a subset of $t$ vertices of $V$. A $t$-tuple $k$-coloring of $H$ is a mapping of its $t$-tuples into $k$ colors. …
View article: Generalized saturation game
Generalized saturation game Open
We study the following game version of the generalized graph Turán problem. For two fixed graphs F and H, two players, Max and Mini, alternately claim unclaimed edges of the complete graph Kn such that the graph G of the claimed edges must…
View article: The constructor-blocker game
The constructor-blocker game Open
Given two graphs F and H, Constructor and Blocker alternately claim unclaimed edges of the complete graph Kn. Constructor?s graph must remain F-free, while Blocker claims edges without restrictions. The game ends when Constructor cannot cl…
View article: Optimizing Symbol Visibility through Displacement
Optimizing Symbol Visibility through Displacement Open
In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positioning in the categorical axis admits some flexibility. This…
View article: Complexity of Maker-Breaker Games on Edge Sets of Graphs
Complexity of Maker-Breaker Games on Edge Sets of Graphs Open
We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the $H$-game. Maker wins if she claims the edges of a perfect matching in the first, and…
View article: On the Multi-Robber Damage Number
On the Multi-Robber Damage Number Open
We study a variant of the Cops and Robbers game on graphs in which the robbers damage the visited vertices, aiming to maximize the number of damaged vertices. For that game with one cop against $s$ robbers a conjecture was made by Carlson,…
View article: Avoider-Enforcer Game is NP-hard
Avoider-Enforcer Game is NP-hard Open
In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enforcer alternate in claiming an unclaimed vertex, until all the vertices of the hypergraph are claimed. Enforcer wins if Avoider claims all vertices of an edge; Avoider …
View article: The Constructor-Blocker Game
The Constructor-Blocker Game Open
We study the following game version of the generalized graph Turán problem. For two fixed graphs $F$ and $H$, two players, Constructor and Blocker, alternately claim unclaimed edges of the complete graph $K_n$. Constructor can only claim e…
View article: Semi‐random graph process
Semi‐random graph process Open
We introduce and study a novel semi‐random multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independe…
View article: The Toucher-Isolator game
The Toucher-Isolator game Open
We introduce a new positional game called `Toucher-Isolator', which is a quantitative version of a Maker-Breaker type game. The playing board is the set of edges of a given graph $G$, and the two players, Toucher and Isolator, claim edges …
View article: Hamiltonian Maker–Breaker Games on Small Graphs
Hamiltonian Maker–Breaker Games on Small Graphs Open
We look at the unbiased Maker-Breaker Hamiltonicity game played on the edge set of a complete graph $K_n$, where Maker's goal is to claim a Hamiltonian cycle. First, we prove that, independent of who starts, Maker can win the game for $n =…
View article: Fast strategies in biased Maker--Breaker games
Fast strategies in biased Maker--Breaker games Open
We study the biased $(1:b)$ Maker--Breaker positional games, played on the edge set of the complete graph on $n$ vertices, $K_n$. Given Breaker's bias $b$, possibly depending on $n$, we determine the bounds for the minimal number of moves,…
View article: Bottleneck Bichromatic Non-crossing Matchings using Orbits.
Bottleneck Bichromatic Non-crossing Matchings using Orbits. Open
Given a set of $n$ red and $n$ blue points in the plane, we are interested in matching red points with blue points by straight line segments so that the segments do not cross. Bottleneck matching is such a matching that minimizes the lengt…
View article: Maker-Breaker games on random geometric graphs
Maker-Breaker games on random geometric graphs Open
In a Maker-Breaker game on a graph G, Breaker and Maker alternately claim edges of G. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider four Maker-Breaker games played o…
View article: Hamiltonian Maker-Breaker games on small graphs
Hamiltonian Maker-Breaker games on small graphs Open
We look at the unbiased Maker-Breaker Hamiltonicity game played on the edge set of a complete graph $K_n$, where Maker's goal is to claim a Hamiltonian cycle. First, we prove that, independent of who starts, Maker can win the game for $n =…
View article: Zero-Error Shift-Correcting and Shift-Detecting Codes.
Zero-Error Shift-Correcting and Shift-Detecting Codes. Open
Motivated by communication scenarios such as timing channels (in queuing systems, molecular communications, etc.) and bit-shift channels (in magnetic recording systems), we study the error control problem in cases where the dominant type o…
View article: Faster Bottleneck Non-crossing Matchings of Points in Convex Position
Faster Bottleneck Non-crossing Matchings of Points in Convex Position Open
Given an even number of points in a plane, we are interested in matching all the points by straight line segments so that the segments do not cross. Bottleneck matching is a matching that minimizes the length of the longest segment. For po…