6 papers · 1 filter
Beyond Trees: The Weighted Center Problem on Gromov Hyperbolic Graphs
Guillaume Ducoffe
The Weighted Center} problem takes as its input a graph together with a profile such that every vertex is mapped to some nonnegative multiplicative weight $Ï(v)…
A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
Guillaume Ducoffe
A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph is the largest distance between a central vertex and the…
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…
On -unimodality of radius functions in graphs: structure and algorithms
Jérémie Chalopin, Victor Chepoi, Feodor Dragan +2
For every weight assignment to the vertices in a graph , the radius function maps every vertex of to its largest weighted distance to the other vertices. The cen…
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…
Practical Computation of Graph VC-Dimension
David Coudert, Mónika Csikós, Guillaume Ducoffe +1
For any set system , a subset is called \emph{shattered} if every results from the intersection of with some set in…