26 citations · 34 across the 15 of their papers we have counts for
18 papers
Weighted Embeddings for Low-Dimensional Graph Representation
Thomas Bläsius, Jean-Pierre von der Heydt, Maximilian Katzmann +1
Learning low-dimensional numerical representations from symbolic data, e.g., embedding the nodes of a graph into a geometric space, is an important concept in machine learning. Whi…
Joint Order Selection, Allocation, Batching and Picking for Large Scale Warehouses
Giorgio Abelli, Maximilian Katzmann, Imran Khan +4
Order picking is the single most cost-intensive activity in picker-to-parts warehouses, and as such has garnered large interest from the scientific community which led to multiple…
Maximal Cliques in Scale-Free Random Graphs
Thomas Bläsius, Maximillian Katzmann, Clara Stegehuis
We investigate the number of maximal cliques, i.e., cliques that are not contained in any larger clique, in three network models: Erdős-Rényi random graphs, inhomogeneous random gr…
On the Giant Component of Geometric Inhomogeneous Random Graphs
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann +2
In this paper we study the threshold model of \emph{geometric inhomogeneous random graphs} (GIRGs); a generative random graph model that is closely related to \emph{hyperbolic rand…
Partitioning the Bags of a Tree Decomposition Into Cliques
Thomas Bläsius, Maximilian Katzmann, Marcus Wilhelm
We consider a variant of treewidth that we call clique-partitioned treewidth in which each bag is partitioned into cliques. This is motivated by the recent development of FPT-algor…
Real-World Networks are Low-Dimensional: Theoretical and Practical Assessment
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +1
Detecting the dimensionality of graphs is a central topic in machine learning. While the problem has been tackled empirically as well as theoretically, existing methods have severa…
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +1
A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to rep…
Deep Distance Sensitivity Oracles
Davin Jeong, Allison Gunby-Mann, Sarel Cohen +5
One of the most fundamental graph problems is finding a shortest path from a source to a target node. While in its basic forms the problem has been studied extensively and efficien…
Using random graphs to sample repulsive Gibbs point processes with arbitrary-range potentials
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +2
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an appro…
Computing Voronoi Diagrams in the Polar-Coordinate Model of the Hyperbolic Plane
Tobias Friedrich, Maximilian Katzmann, Leon Schiller
A Voronoi diagram is a basic geometric structure that partitions the space into regions associated with a given set of sites, such that all points in a region are closer to the cor…
Towards Explainable Real Estate Valuation via Evolutionary Algorithms
Sebastian Angrick, Ben Bals, Niko Hastrich +6
Human lives are increasingly influenced by algorithms, which therefore need to meet higher standards not only in accuracy but also with respect to explainability. This is especiall…
Algorithms for hard-constraint point processes via discretization
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +2
We study algorithmic applications of a natural discretization for the hard-sphere model and the Widom-Rowlinson model in a region . These models are…
Strongly Hyperbolic Unit Disk Graphs
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann +1
The class of Euclidean unit disk graphs is one of the most fundamental and well-studied graph classes with underlying geometry. In this paper, we identify this class as a special c…
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann
Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of…
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann +3
Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks…
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich +1
The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasona…
A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints
Álvaro Parra, Tat-Jun Chin, Frank Neumann +2
A popular paradigm for 3D point cloud registration is by extracting 3D keypoint correspondences, then estimating the registration function from the correspondences using a robust a…
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich +3
A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It h…