3 citations · 7 across the 6 of their papers we have counts for
6 papers
The Depth-Restricted Rectilinear Steiner Arborescence Problem is NP-complete
Jens Maßberg
In the rectilinear Steiner arborescence problem the task is to build a shortest rectilinear Steiner tree connecting a given root and a set of terminals which are placed in the plan…
The Union-Closed Sets Conjecture for Small Families
Jens Maßberg
We prove that the union-closed sets conjecture is true for separating union-closed families with $|\mathcal{A}| \leq 2\left(m+\frac{m}{\log_2(m)-\log_2\log_2(m)}\righ…
Solitaire Chess is NP-complete
Jens Maßberg
"Solitaire Chess" is a logic puzzle published by Thinkfun, that can be seen as a single person version of traditional chess. Given a chess board with some chess pieces of the same…
The rectilinear Steiner tree problem with given topology and length restrictions
Jens Maßberg
We consider the problem of embedding the Steiner points of a Steiner tree with given topology into the rectilinear plane. Thereby, the length of the path between a distinguished te…
The "Game about Squares" is NP-hard
Jens Maßberg
In the "Game about Squares" the task is to push unit squares on an integer lattice onto corresponding dots. A square can only be moved into one given direction. When a square is pu…
Generalized Huffman Coding for Binary Trees with Choosable Edge Lengths
Jens Maßberg
In this paper we study binary trees with choosable edge lengths, in particular rooted binary trees with the property that the two edges leading from every non-leaf to its two child…