62 citations · 316 across the 38 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.DS2011
Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time
Jakub Łącki, Piotr Sankowski
We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorith…
cs.DS2011
Approximation Algorithms for Union and Intersection Covering Problems
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi +3
In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST…