Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Linear-Time Multilevel Graph Partitioning via Edge Sparsification
Lars Gottesbüren, Nikolai Maas, Dominik Rosch +2
The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as singl…
cs.DS2024
Engineering Optimal Parallel Task Scheduling
Matthew Akram, Nikolai Maas, Peter Sanders +1
The NP-hard scheduling problem P||C_max encompasses a set of tasks with known execution time which must be mapped to a set of identical machines such that the overall completion ti…