8 citations · 12 across the 4 of their papers we have counts for
3 papers · 1 filter
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…
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…
Diameter computation on -minor free graphs and graphs of bounded (distance) VC-dimension
Guillaume Ducoffe, Michel Habib, Laurent Viennot
We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-…