A Platform
for combinatorial & geometric computingA 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.
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.
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).
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).
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 ResearchThe 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