research
∙
04/07/2023
Temporalizing digraphs via linear-size balanced bi-trees
In a directed graph D on vertex set v_1,… ,v_n, a forward arc is an arc ...
share
research
∙
04/03/2023
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
A temporal graph is a graph in which edges are assigned a time label. Tw...
research
∙
02/15/2023
Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor
In this paper, we study temporal graphs arising from mobility models whe...
research
∙
01/30/2023
Breadth-First Depth-Next: Optimal Collaborative Exploration of Trees with Low Diameter
We consider the problem of collaborative tree exploration posed by Fraig...
research
∙
11/22/2022
Minimum-Cost Temporal Walks under Waiting-Time Constraints in Linear Time
In a temporal graph, each edge is available at specific points in time. ...
research
∙
11/16/2021
Hyperbolicity Computation through Dominating Sets
Hyperbolicity is a graph parameter related to how much a graph resembles...
research
∙
11/16/2021
On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation
We consider the problem of assigning appearing times to the edges of a d...
research
∙
04/26/2021
Enumeration of Far-Apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation
Hyperbolicity is a graph parameter which indicates how much the shortest...
research
∙
01/06/2021
On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks
A weighted point-availability time-dependent network is a list of tempor...
research
∙
10/24/2019
A Comparative Study of Neural Network Compression
There has recently been an increasing desire to evaluate neural networks...
research
∙
10/08/2019
Fast Diameter Computation within Split Graphs
When can we compute the diameter of a graph in quasi linear time? We add...
research
∙
07/09/2019
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
We propose to study unweighted graphs of constant distance VC-dimension ...
research
∙
06/21/2019
Fast Public Transit Routing with Unrestricted Walking through Hub Labeling
We propose a novel technique for answering routing queries in public tra...
research
∙
02/19/2019
Hardness of exact distance queries in sparse graphs through hub labeling
A distance labeling scheme is an assignment of bit-labels to the vertice...
research
∙
09/06/2018
Efficient Loop Detection in Forwarding Networks and Representing Atoms in a Field of Sets
The problem of detecting loops in a forwarding network is known to be NP...
research
∙
03/19/2018
Exact Distance Oracles Using Hopsets
For fixed h ≥ 2, we consider the task of adding to a graph G a set of we...
research
∙
03/13/2018