2 citations · 2 across the 3 of their papers we have counts for
4 papers
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann +5
We consider very natural "fence enclosure" problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set of points in th…
Approximation Schemes for Independent Set and Sparse Subsets of Polygons
Anna Adamaszek, Sariel Har-Peled, Andreas Wiese
We present an -approximation algorithm with quasi-polynomial running time for computing the maximum weight independent set of polygons out of a given set of polygo…
Large-girth roots of graphs
Anna Adamaszek, Michal Adamaszek
We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r+3,…
PTAS for k-tour cover problem on the plane for moderately large values of k
Anna Adamaszek, Artur Czumaj, Andrzej Lingas
Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem…