1 citations · 1 across the 12 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.DS2018
Optimal strategies for patrolling fences
Bernhard Haeupler, Fabian Kuhn, Anders Martinsson +2
A classical multi-agent fence patrolling problem asks: What is the maximum length of a line that agents with maximum speeds can patrol if each point on the…