4 papers
An Approximation Algorithm for Graph Label Selection
Josia John, Simon Meierhans, Maximilian Probst Gutenberg
In the graph label selection problem, one is given an -vertex graph and a budget , and seeks to select vertices whose labels enable accurate prediction of the labels on t…
Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
Simon Meierhans, Maximilian Probst Gutenberg
Whether a graph is connected is arguably its most fundamental property. Naturally, connectivity was the first characteristic studied for dynamic graphs, i.e. graphs that…
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions to an -edge graph that is…
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg +1
Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph , a near-optimal -expander decomposition is…