A cop and robber game on edge-periodic temporal graphs
(2024)
Journal Article
Erlebach, T., Morawietz, N., Spooner, J. T., & Wolf, P. (2024). A cop and robber game on edge-periodic temporal graphs. Journal of Computer and System Sciences, 144, Article 103534. https://doi.org/10.1016/j.jcss.2024.103534
Outputs (6)
Parameterized temporal exploration problems (2023)
Journal Article
Erlebach, T., & Spooner, J. T. (2023). Parameterized temporal exploration problems. Journal of Computer and System Sciences, 135, 73-88. https://doi.org/10.1016/j.jcss.2023.01.003In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph G admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices.... Read More about Parameterized temporal exploration problems.
Round-competitive algorithms for uncertainty problems with parallel queries (2022)
Journal Article
Erlebach, T., Hoffmann, M., & de Lima, M. S. (2023). Round-competitive algorithms for uncertainty problems with parallel queries. Algorithmica, 85(2), 406-443. https://doi.org/10.1007/s00453-022-01035-6In computing with explorable uncertainty, one considers problems where the values of some input elements are uncertain, typically represented as intervals, but can be obtained using queries. Previous work has considered query minimization in the sett... Read More about Round-competitive algorithms for uncertainty problems with parallel queries.
Exploration of k-Edge-Deficient Temporal Graphs (2022)
Journal Article
Erlebach, T., & Spooner, J. T. (2022). Exploration of k-Edge-Deficient Temporal Graphs. Acta Informatica, 59(4), 387-407. https://doi.org/10.1007/s00236-022-00421-5A temporal graph with lifetime L is a sequence of L graphs G1, . . . , GL, called layers, all of which have the same vertex set V but can have different edge sets. The underlying graph is the graph with vertex set V that contains all the edges that a... Read More about Exploration of k-Edge-Deficient Temporal Graphs.
Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings (2022)
Journal Article
Luo, K., Erlebach, T., & Xu, Y. (2022). Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings. Discrete Applied Mathematics, 313, 53-66. https://doi.org/10.1016/j.dam.2022.01.016We study an online scheduling problem that is motivated by applications such as car-sharing. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using a single server (car). Each ride request specifies the pi... Read More about Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings.
On the fast delivery problem with one or two packages (2020)
Journal Article
Carvalho, I. A., Erlebach, T., & Papadopoulos, K. (2021). On the fast delivery problem with one or two packages. Journal of Computer and System Sciences, 115, 246-263. https://doi.org/10.1016/j.jcss.2020.09.002