.png){kind=icon}
.png){kind=icon}
Return
Parameterized Restless Temporal Path
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-04700-7_7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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) algorithms for vertex reachability problems in temporal graphs. We study this newly introduced parameter for the problem of restless temporal paths, in which the waiting time at each node is restricted. In this article, we prove that, in the interval model, where arcs are present for entire time intervals, finding a restless temporal path is NP-hard even if the vertex-interval-membership-width is equal to three. We exhibit FPT algorithms for the point model, where arcs are present at specific points in time, both with uniform delay one and arbitrary positive delays. In the latter case, this comes with a slight additional computational cost.
Keywords:
Temporal graphs
Restless temporal paths
Parameterized algorithms
Interval-membership-width
Journal
F
IF:
0
Papers:
30
Citations:
0