Outputs (3)

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.

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

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.