All Outputs (12)

Scheduling with Obligatory Tests (2024)
Presentation / Conference Contribution
Dogeas, K., Erlebach, T., & Liang, Y.-C. (2024, September). Scheduling with Obligatory Tests. Presented at 32nd Annual European Symposium on Algorithms (ESA 2024), Egham, United Kingdom

Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the tim... Read More about Scheduling with Obligatory Tests.

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty (2024)
Presentation / Conference Contribution
Bampis, E., Dogeas, K., Erlebach, T., Megow, N., Schlöter, J., & Trehan, A. (2024, August). Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. Presented at International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024), London, UK

We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algo... Read More about Competitive Query Minimization for Stable Matching with One-Sided Uncertainty.

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous (2024)
Presentation / Conference Contribution
Dogeas, K., Erlebach, T., Kammer, F., Meintrup, J., & Moses Jr, W. K. (2024, July). Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. Presented at 51st EATCS International Colloquium on Automata, Languages and Programming, Tallinn, Estonia

Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization (2024)
Presentation / Conference Contribution
Erlebach, T., Morawietz, N., & Wolf, P. (2024, June). Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Patras, Greece

In the periodic temporal graph realization problem introduced by Klobas et al. [SAND '24] one is given a period Δ and an n× n matrix D of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period... Read More about Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization.

Sorting and Hypergraph Orientation under Uncertainty with Predictions (2023)
Presentation / Conference Contribution
Erlebach, T., de Lima, M., Megow, N., & Schlöter, J. (2023, August). Sorting and Hypergraph Orientation under Uncertainty with Predictions. Presented at Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023), Macao, S.A.R., China

Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to min... Read More about Sorting and Hypergraph Orientation under Uncertainty with Predictions.

List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs (2023)
Presentation / Conference Contribution
Baklan Sen, B., Diner, Ö. Y., & Erlebach, T. (2023, December). List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs. Presented at 29th International Computing and Combinatorics Conference (COCOON 2023), Honolulu, Hawaii, USA

Given a graph G = (V, E) and a list of available colors L(v) for each vertex v ∈ V, where L(v) ⊆ {1, 2, . . . , k}, LIST k-COLORING refers to the problem of assigning colors to the vertices of G so that each vertex receives a color from its own list... Read More about List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs.

Package Delivery Using Drones with Restricted Movement Areas (2022)
Presentation / Conference Contribution
Erlebach, T., Luo, K., & Spieksma, F. C. (2022, December). Package Delivery Using Drones with Restricted Movement Areas. Presented at 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Seoul, Korea

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty (2022)
Presentation / Conference Contribution
Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2022, September). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. Presented at 30th Annual European Symposium on Algorithms (ESA 2022), Potsdam, Germany

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.

Parameterized temporal exploration problems (2022)
Presentation / Conference Contribution
Erlebach, T., & Spooner, J. T. (2022, March). Parameterized temporal exploration problems. Presented at 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), Virtual Conference

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.

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty (2021)
Presentation / Conference Contribution
Bampis, E., Dürr, C., Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2021, December). Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. Presented at 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon, Portugal (Virtual Conference)

Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node... Read More about Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty.

Exploration of k-Edge-Deficient Temporal Graphs (2021)
Presentation / Conference Contribution
Erlebach, T., & Spooner, J. T. (2021, December). Exploration of k-Edge-Deficient Temporal Graphs. Presented at WADS 2021: Algorithms and Data Structures

Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries (2021)
Presentation / Conference Contribution
Erlebach, T., Hoffmann, M., & de Lima, M. S. (2021, December). Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. Presented at 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Saarbrücken, Germany