1 citations · 1 across the 3 of their papers we have counts for
5 papers
A Linear-Time Algorithm for the Unbiased Claw Game on Graphs with Maximum Degree 4
Julian Christoph Brinkmann
We study the unbiased Maker-Breaker -game, the unbiased claw game, played on the edge set of a general graph . In this game, Maker and Breaker alternatingly claim edges…
Faster Algorithms for Deciding the Unbiased Maker-Breaker Triangle Game on General Graphs
Julian Christoph Brinkmann, Anand Srivastav
In this paper, we present new polynomial-time algorithms for determining the winner of the unbiased triangle game played on the edge set of general graphs. To that end, we propose…
On the Complexity of the Minimum-()-Shortcut Problem
Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt +1
We consider the Minimum-- problem (), where the goal is to find the smallest set of shortcut edges such that every ver…
The Complexity of Color-constrained Paths in Semicomplete Multipartite Digraphs
Julian Brinkmann
Every semicomplete multipartite digraph contains a quasi-Hamiltonian path, but the problem of finding a quasi-Hamiltonian path with prescribed start and end vertex is NP-complete e…
The Parametrised Complexity of Counting Small Sub-Hypergraphs
Marco Bressan, Julian Brinkmann, Holger Dell +2
Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has b…