research
∙
07/21/2023
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Despite extensive research on distance oracles, there are still large ga...
share
research
∙
05/27/2023
Finding Diameter-Reducing Shortcuts in Trees
In the k-Diameter-Optimally Augmenting Tree Problem we are given a tree ...
research
∙
05/19/2023
Approximate Distance Sensitivity Oracles in Subquadratic Space
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch ...
research
∙
05/12/2023
Temporal Network Creation Games
Most networks are not static objects, but instead they change over time....
research
∙
05/11/2023
Schelling Games with Continuous Types
In most major cities and urban areas, residents form homogeneous neighbo...
research
∙
05/05/2023
Fault-Tolerant ST-Diameter Oracles
We study the problem of estimating the ST-diameter of a graph that is su...
research
∙
04/27/2023
Compact Distance Oracles with Large Sensitivity and Low Stretch
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch ...
research
∙
06/22/2022
Sparse Temporal Spanners with Low Stretch
A temporal graph is an undirected graph G=(V,E) along with a function th...
research
∙
04/26/2022
Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games
Residential segregation in metropolitan areas is a phenomenon that can b...
research
∙
04/22/2022
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
We construct data structures for extremal and pairwise distances in dire...
research
∙
12/06/2021
Fixed-Parameter Sensitivity Oracles
We combine ideas from distance sensitivity oracles (DSOs) and fixed-para...
research
∙
07/07/2021
Space-Efficient Fault-Tolerant Diameter Oracles
We design f-edge fault-tolerant diameter oracles (f-FDOs). We preprocess...
research
∙
06/29/2021
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Given a graph with a source vertex s, the Single Source Replacement Path...
research
∙
06/23/2021
Finding single-source shortest p-disjoint paths: fast computation and sparse preservers
Let G be a directed graph with n vertices, m edges, and non-negative edg...
research
∙
12/11/2020
Selfish Creation of Social Networks
Understanding real-world networks has been a core research endeavor thro...
research
∙
09/23/2020
Fair Tree Connection Games with Topology-Dependent Edge Cost
How do rational agents self-organize when trying to connect to a common ...
research
∙
05/06/2020
Topological Influence and Locality in Swap Schelling Games
Residential segregation is a wide-spread phenomenon that can be observed...
research
∙
05/01/2020
Cutting Bamboo Down to Size
This paper studies the problem of programming a robotic panda gardener t...
research
∙
04/15/2019
Geometric Network Creation Games
Network Creation Games are a well-known approach for explaining and anal...
research
∙
09/24/2018
Almost optimal algorithms for diameter-optimally augmenting trees
We consider the problem of augmenting an n-vertex tree with one shortcu...
research
∙
07/09/2018
An Interesting Structural Property Related to the Problem of Computing All the Best Swap Edges of a Tree Spanner in Unweighted Graphs
In this draft we prove an interesting structural property related to the...
research
∙
07/03/2018
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
Given a 2-edge connected undirected graph G with n vertices and m edges,...
research
∙
04/28/2018
New algorithms for Steiner tree reoptimization
Reoptimization is a setting in which we are given an (near) optimal sol...
research
∙
10/04/2017