1 citations · 1 across the 5 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
Jonas Lill, Kalina Petrova, Simon Weber
MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertice…
cs.DS2022
Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs
Simon Weber, Joel Widmer
Algorithms for finding the sink in Unique Sink Orientations (USOs) of the hypercube can be used to solve many algebraic and geometric problems, most importantly including the P-Mat…