research
∙
09/06/2023
Maximal Cliques in Scale-Free Random Graphs
We investigate the number of maximal cliques, i.e., cliques that are not...
share
research
∙
06/16/2023
An Efficient Algorithm for Power Dominating Set
The problem Power Dominating Set (PDS) is motivated by the placement of ...
research
∙
06/15/2023
On the Giant Component of Geometric Inhomogeneous Random Graphs
In this paper we study the threshold model of geometric inhomogeneous ra...
research
∙
02/17/2023
Partitioning the Bags of a Tree Decomposition Into Cliques
We consider a variant of treewidth that we call clique-partitioned treew...
research
∙
02/15/2023
Dynamic Flows with Time-Dependent Capacities
Dynamic network flows, sometimes called flows over time, extend the noti...
research
∙
01/13/2023
Recognizing Unit Disk Graphs in Hyperbolic Geometry is ∃ℝ-Complete
A graph G is a (Euclidean) unit disk graph if it is the intersection gra...
research
∙
09/30/2022
Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks
A common technique to speed up shortest path queries in graphs is to use...
research
∙
05/30/2022
On the External Validity of Average-Case Analyses of Graph Algorithms
The number one criticism of average-case analysis is that we do not actu...
research
∙
10/22/2021
An Efficient Branch-and-Bound Solver for Hitting Set
The hitting set problem asks for a collection of sets over a universe U ...
research
∙
07/12/2021
Routing in Strongly Hyperbolic Unit Disk Graphs
Greedy routing has been studied successfully on Euclidean unit disk grap...
research
∙
03/24/2021
The Complexity of Dependency Detection and Discovery in Relational Databases
Multi-column dependencies in relational databases come associated with t...
research
∙
02/19/2021
The Flip Schelling Process on Random Geometric and Erdös-Rényi Graphs
Schelling's classical segregation model gives a coherent explanation for...
research
∙
10/06/2020
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
Finding a minimum vertex cover in a network is a fundamental NP-complete...
research
∙
09/21/2020
Efficiently Computing Maximum Flows in Scale-Free Networks
We study the maximum-flow/minimum-cut problem on scale-free networks, i....
research
∙
08/24/2020
A Strategic Routing Framework and Algorithms for Computing Alternative Paths
Traditional navigation services find the fastest route for a single driv...
research
∙
07/30/2020
Synchronized Planarity with Applications to Constrained Planarity Problems
We introduce the problem Synchronized Planarity. Roughly speaking, its i...
research
∙
04/15/2020
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
Satisfiability is considered the canonical NP-complete problem and is us...
research
∙
10/01/2019
The Minimization of Random Hypergraphs
We investigate the maximum-entropy model B_n,m,p for random n-vertex, m-...
research
∙
05/29/2019
Understanding the Effectiveness of Data Reduction in Public Transportation Networks
Given a public transportation network of stations and connections, we wa...
research
∙
05/16/2019
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs
Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs...
research
∙
04/29/2019
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
The VertexCover problem is proven to be computationally hard in differen...
research
∙
05/07/2018
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
A common way to accelerate shortest path algorithms on graphs is the use...
research
∙
05/03/2018