7 papers
Membership and Conjugacy in Inverse Semigroups
Lukas Fleischer, Florian Stober, Alexander Thumm +1
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the me…
Finite groups with geodetic Cayley graphs
Murray Elder, Adam Piggott, Florian Stober +2
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups…
Geodetic Graphs: Experiments and New Constructions
Florian Stober, Armin Weiß
In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a wide range o…
Lower Bounds for Sorting 16, 17, and 18 Elements
Florian Stober, Armin Weiß
It is a long-standing open question to determine the minimum number of comparisons that suffice to sort an array of elements. Indeed, before this work has been kn…
The Power Word Problem in Graph Products
Markus Lohrey, Florian Stober, Armin Weiß
The power word problem for a group asks whether an expression , where the are words over a finite set of generators of and the binar…
On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
Jacqueline W. Daykin, Dominik Köppl, David Kübel +1
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries…
On the Average Case of MergeInsertion
Florian Stober, Armin Weiß
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of compa…