lu.se

Computer Science

Faculty of Engineering, LTH

Denna sida på svenska This page in English This page in English

Algorithms

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.

Computational Geometry

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

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 ).

Parallel, Distributed and Sequential Graph Algorithms

Efficient exact or approximation algorithms for subgraph isomorphism, graph packing, pattern matching and for fast network broadcasting.

Computational Biology

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

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

Contact

E-mail: Andrzej.Lingas, followed by at-sign, followed by cs (dot) lth (dot) se

Postal address Box 118, 221 00 Lund

Phone: ++46-46-2224519

Fax (the same number for the whole staff): ++46-46-131021

Office at the campus: room 2420 in Building E ("E-huset"), Ole Römers väg 3