## A Platform for combinatorial & geometric computing

A unique tool fills a gap for software developers in large application domains, such as traffic scheduling, resource management and image processing.

### Overview

Combinatorial and geometric computing is a core area of computer science. Dealing with objects such as graphs, sequences, dictionaries, trees, points, flows, matchings, segments, shortest paths etc., the subject forms the basis for application areas such as discrete optimisation, resource scheduling, traffic control and computer-aided design. In contrast to other areas of computing, there is no standard library of the data structures and algorithms used. Under the ALCOM project a comprehensive library of algorithms and data structures in this area of computing has been compiled in a form which is accessible to non-experts. The library, called LEDA (Library of Efficient Data Types and Algorithms), contains all of the relevant building blocks in an easy-to-use and efficient form. LEDA is implemented in C++, and can be used with almost any C++ compiler. It is continuously updated with the most recent and efficient implementations.

### Business perspective

LEDA has very broad application potential, particularly since no other library of its type currently exists. The algorithms and data types included are general and flexible, and can therefore be incorporated in a wide range of applications. This is illustrated by the fact that LEDA is used not only as a kernel or platform for a large variety of research purposes, but has found commercial applications in companies such as the Ford Motor Company, Sony Electronics, Lufthansa Systems and MCI Telecorporation. LEDA is available, in both compiled and source code form, under licence for industrial and commercial use from LEDA Software GmbH. The system is also distributed free of charge, by ftp, for educational and academic research use (from ftp.mpi-sb.mpg.de in /pub/LEDA).

### Technical perspective

The LEDA (Library of Efficient Data structures and Algorithms) essentially consists of four parts: Basic Data Structures, including most data types in the textbooks in the area of combinatorial computation; Graphs, including many graph and network algorithms written in the textbooks of the area; Geometric Computing, including many algorithms that use arbitrary precision arithmetic and which can handle degenerate cases; and Graphics, which can easily be adapted to many common interfaces (X11, Windows 32, MS/DOS, OS/2). Applications LEDA is used in institutes for a wide range of disciplines, including astrophysics, biology, chemistry, computer science, electronics, evolution research, machine building, mathematics, microelectronics and social science. Several telecommunications companies, for instance France Telecom, MCI (USA), Comptel (Finland) and E-Plus Mobilfunk (Germany), make use of the graph algorithms. Several companies use the geometric part of Computer Aided Design, for instance Cadabra (Canada) and MUS (Germany).

### Contact Point

tel +49-681-9325-123 -- fax +49-681-9325-199

e-mail uhrig@mpi-sb.mpq.de

www http://www.mpi-sb.mpg.de/LEDA/leda.html

Research Area: Long Term Research

Project: ALCOM

Keywords: combinatorial computing, geometric computing, algorithms, data structures, graphs

| Project Participants
Aarhus Universitet - DK
Universitat Politecnica de Catalunya - E
Freie Universität Berlin - D
University of Dublin - IR
EHESS - F
INRIA-Paris - F
INRIA-Sophia Antipolis - F
Universität Paderborn - D
University of Patras - GR
Universita degli Studi di Roma "La Sapienza" - I
Max-Planck-Institut für Informatik - D
Rjiksuniversiteit Utrecht - NL
University of Warwick - UK

### home page | Results Zone | IT Solutions | Application Areas | Research Areas | Long Term Research

The URL for this page is http://www.cordis.lu/esprit/src/results/res_area/ltr/ltr1.htm
This page was last updated on 22 November 1996, and is maintained by esprit@dg3.cec.be