4 papers
Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
Guillaume Aubian, Filippo Brunelli, Feodor F Dragan +4
Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal as…
Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1
In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomial-time algorithms. We specifically target radius (minimum eccentricity)…
Bow Metrics and Hyperbolicity
Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1
A ()-bow metric was defined in (Dragan & Ducoffe, 2023) as a far reaching generalization of an -metric (which is equivalent to a ()-bow metric). A graph …
Quasilinear-time eccentricities computation, and more, on median graphs
Pierre Bergé, Guillaume Ducoffe, Michel Habib
Computing the diameter, and more generally, all eccentricities of an undirected graph is an important problem in algorithmic graph theory and the challenge is to identify graph cla…