6 papers
Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics
Justine Cauvi, Nils Morawietz, Laurent Viennot
In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a…
Parameterized Restless Temporal Path
Justine Cauvi, Laurent Viennot
Recently, Bumpus and Meeks introduced a purely temporal parameter, called vertex-interval-membership-width, which is promising for the design of fixed-parameter tractable (FPT) alg…
Making Temporal Betweenness Computation Faster and Restless
Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot
Buß et al [KDD 2020] recently proved that the problem of computing the betweenness of all nodes of a temporal graph is computationally hard in the case of foremost and fastest path…
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…
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 is…
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-…