10 papers
Algorithm Engineering for Cut Problems
Alexander Noe
Graphs are a natural representation of data from various contexts, such as social connections, the web, road networks, and many more. In the last decades, many of these networks ha…
Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm Performs Best in Practice?
Monika Henzinger, Alexander Noe
Fully dynamic graph algorithms that achieve polylogarithmic or better time per operation use either a hierarchical graph decomposition or random-rank based approach. There are so f…
New instances for maximum weight independent set from a vehicle routing application
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve…
Practical Fully Dynamic Minimum Cut Algorithms
Monika Henzinger, Alexander Noe, Christian Schulz
We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical…
Recent Advances in Practical Data Reduction
Faisal Abu-Khzam, Sebastian Lamm, Matthias Mnich +3
Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has res…
Faster Parallel Multiterminal Cuts
Monika Henzinger, Alexander Noe, Christian Schulz
We give an improved branch-and-bound solver for the multiterminal cut problem, based on the recent work of Henzinger et al.. We contribute new, highly effective data reduction rule…