Papers accepted at MFCS 2024 and ESA 2024

Two papers by the group were accepted at MFCS and ESA, respectively.

In On the Complexity of Community-aware Network Sparsification, coauthored by Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer, we study the problem of removing edges from a graph while maintaining certain connectivity properties for a set of given communities. We show, for example, that the best case when the graph is a tree can be solved in polynomial time. This paper will be presented at MFCS 2024External link in Bratislava.

In SubModST: A Fast Generic Solver for Submodular Maximization with Size Constraints, coauthored by Henning Martin Woydt, Christian Komusiewicz and Frank Sommer we present a solver for a generic class of hard optimization problems where we want to choose a small set from a universe that maximizes a given objective function. The new solver is several orders of magnitudes faster than previous generic solvers for this problem. This paper is based on Henning's Master's thesis and will be presented at ESA 2024External link held at Royal Holloway, University of London.