15 citations · 45 across the 12 of their papers we have counts for
12 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…
The Art Gallery Problem is -complete
Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The…
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…
Irrational Guards are Sometimes Needed
Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a si…
Hardness of approximation for strip packing
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk +1
Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing…
Almost all trees are almost graceful
Anna Adamaszek, Peter Allen, Codrut Grosu +1
The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labelled by using the numbers {1,2,...,n} in such a way that t…
Algorithmic and Hardness Results for the Colorful Components Problems
Anna Adamaszek, Alexandru Popa
In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges fr…
A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
Anna Adamaszek, Andreas Wiese
The Maximum Weight Independent Set of Polygons problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the 2-dimensional plane, the goal is…
Approximation Schemes for Maximum Weight Independent Set of Rectangles
Anna Adamaszek, Andreas Wiese
In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight sub…
Uniqueness of graph square roots of girth six
Anna Adamaszek, Michal Adamaszek
We prove that if two graphs of girth at least 6 have isomorphic squares, then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and H…
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…