research
∙
05/04/2023
α_i-Metric Graphs: Radius, Diameter and all Eccentricities
We extend known results on chordal graphs and distance-hereditary graphs...
share
research
∙
02/22/2023
Pattern detection in ordered graphs
A popular way to define or characterize graph classes is via forbidden s...
research
∙
11/06/2022
Balancing graph Voronoi diagrams with one more vertex
Let G=(V,E) be a graph with unit-length edges and nonnegative costs assi...
research
∙
09/26/2022
Obstructions to faster diameter computation: Asteroidal sets
An extremity is a vertex such that the removal of its closed neighbourho...
research
∙
10/06/2021
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
On sparse graphs, Roditty and Williams [2013] proved that no O(n^2-ε)-ti...
research
∙
02/16/2021
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
A graph is Helly if every family of pairwise intersecting balls has a no...
research
∙
01/10/2021
Beyond Helly graphs: the diameter problem on absolute retracts
Characterizing the graph classes such that, on n-vertex m-edge graphs in...
research
∙
11/17/2020
Optimal diameter computation within bounded clique-width graphs
Coudert et al. (SODA'18) proved that under the Strong Exponential-Time H...
research
∙
10/30/2020
Distance problems within Helly graphs and k-Helly graphs
The ball hypergraph of a graph G is the family of balls of all possible ...
research
∙
10/29/2020
Around the diameter of AT-free graphs
A graph algorithm is truly subquadratic if it runs in O(m^b) time on con...
research
∙
10/29/2020
Isometric embeddings in trees and their use in the diameter problem
We prove that given a discrete space with n points which is either embed...
research
∙
10/29/2020
Eccentricity queries and beyond using Hub Labels
Hub labeling schemes are popular methods for computing distances on road...
research
∙
10/23/2019
A story of diameter, radius and Helly property
A graph is Helly if every family of pairwise intersecting balls has a no...
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
∙
10/24/2018
Faster approximation algorithms for computing shortest cycles on weighted graphs
Given an n-vertex m-edge graph G with non negative edge-weights, the gir...
research
∙
10/04/2018
Polynomial-time Recognition of 4-Steiner Powers
The kth-power of a given graph G=(V,E) is obtained from G by adding an e...
research
∙
09/17/2018
Equivalence between pathbreadth and strong pathbreadth
We say that a given graph G = (V, E) has pathbreadth at most ρ, denoted ...
research
∙
04/25/2018
The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes
We address the following general question: given a graph class C on whic...
research
∙
04/25/2018
A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs
We present a quasi linear-time algorithm for Maximum Matching on distanc...
research
∙
03/16/2018
Fast approximation and exact computation of negative curvature parameters of graphs
In this paper, we study Gromov hyperbolicity and related parameters, tha...
research
∙
07/17/2017