Algorithms

Current and former members of the group.

 A selected set of our publications

The construction and analysis of algorithms and data structures is a basic and very important part of modern computer science. Its importance increases also by the rapid development of more powerful and faster computers. All computer programs can be described as algorithms that operate on a structured set of data, or as a concatenation of such algorithms. To construct a large program with a reasonable time and space consumption it is essential to have efficient solutions to the problem parts.

The main areas of research studied by the algorithm group fall into five mutually interrelated categories, namely computational geometry, geometric graph algorithms,  parallel, distributed and sequential graph algorithms, computational biology,  searching and sorting .They are structured as follows:

1. Computational Geometry
Efficient algorithms  or approximation algorithms  for Voronoi diagrams and triangulations,  optimal decompositions and motion planning. See also Geometric Graph Algorithms.

2. Geometric Graph Algorithms
Efficient approximation algorithms for Euclidean network problems including minimum-cost multi-connectivity, fault tolerant spanners and ``traveling salesperson''--type problems (also in the kinetic setting where the input objects move with different velocities in different directions ).

3. Parallel, Distributed and Sequential Graph Algorithms
Efficient exact or approximation algorithms for subgraph isomorphism, graph packing, pattern matching and for fast network broadcasting.

4. Computational Biology
Efficient methods for inferring evolutionary trees and efficient approximati on algorithms for string center problems.

5.  Searching and Sorting
Lower bounds and efficient construction methods  for  tree-like data structures  for such basic problems as geometric range searching, priority search trees, static tree union-find  and  several problems from  dynamic computational geometry. Efficient sequential and parallel algorithms for sorting, adaptive sorting and merging.

Sorting, searching and graph algorithms are classical topics in computer science. Computational geometry, parallel and distributed graph algorithms, and computational biology belong to the new frontier of computer science inspired by the rapid development of graphics, robotics, VLSI and parallel computing in recent years. The considered problems have applications in robotics, communication, databases, computer graphics, numerical analysis (in particular, terrain interpolation), cartography, chemistry, biology, and combinatorial optimization.