(Re)packing Equal Disks into Rectangle.

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem.

Diverse collections in matroids and graphs.

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid , a weight function , and integers . The task is to decide if there is a collection of of such that the weight of the symmetric difference of any pair of these bases is at least .

Parameterized Complexity of Directed Spanner Problems.

We initiate the parameterized complexity study of minimum -spanner problems on directed graphs. For a positive integer , a multiplicative -spanner of a (directed) graph is a spanning subgraph such that the distance between any two vertices in is at most times the distance between these vertices in , that is, keeps the distances in up to the distortion (or stretch) factor . An additive -spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter , that is, the distances in and differ by at most .

Finding Cactus Roots in Polynomial Time.

A graph is a square root of a graph , or equivalently, is the square of , if can be obtained from by adding an edge between any two vertices in that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. The problem of testing whether a graph admits a square root which belongs to some specified graph class is called the -Square Root problem.