6 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)…
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 pat…
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 …