All Outputs (5)

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty (2022)
Conference Proceeding
Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2022). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms (ESA 2022) (12:1-12:16). https://doi.org/10.4230/lipics.esa.2022.12

We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundam... Read More about Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty.

Package Delivery Using Drones with Restricted Movement Areas (2022)
Conference Proceeding
Erlebach, T., Luo, K., & Spieksma, F. C. (in press). Package Delivery Using Drones with Restricted Movement Areas. In S. W. Bae, & H. Park (Eds.), . https://doi.org/10.4230/lipics.isaac.2022.49

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-5

A 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.

Parameterized temporal exploration problems (2022)
Conference Proceeding
Erlebach, T., & Spooner, J. T. (2022). Parameterized temporal exploration problems. In J. Aspnes, & O. Michail (Eds.), . https://doi.org/10.4230/lipics.sand.2022.15

In 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.

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.016

We 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.