A Library of Efficient Datatypes and Algorithms
LEDA extension packages (LEPs) extend LEDA into particular application domains and areas of algorithmics not covered by the core system. LEPs satisfy the LEP requirements. It is the sole decision of the LEDA Board whether a package qualifies as a LEDA extension package.
The LEDA board advices potential contributors of LEPs to inform the board well in advance of their plans. The Algorithmic Solutions GmbH is interested in integrating successful LEPs into its spectrum of products.
See Extension Packages of LEDA for the currently available packages. Users can get
Linear Programming is the task of opimizing a linear objective function
under a set of linear constraints.
The package is under construction at the Max-Planck-Institute für Informatik (Carsten Kwappik). There is a prototype interface available for this package.
Many problems on graphs are NP-complete. This package provides approximation algorithms for some NP-complete problems on graphs. It is under construction at the Max-Planck-Institute für Informatik (Naveen Garg).
Let G= (V,E) be an undirected graph and let w be a non-negative cost
function on the edges of G. For any subset
of the vertices of
G a Steiner tree T for S is a subtree of G connecting the vertices in
S. The cost of the Steiner tree is the sum of the cost of its edges. A
Steiner tree is minimal if is has minimum cost among all Steiner tree.
The Steiner tree package contains functions that compute optimal Steiner trees for small sets S and compute approximate Steiner trees any set S. The package was written by Georg Althaus at the MPII Saarbrücken.
LEDA extension packages must satisfy the following requirements:
The LEP integration follows these steps:
The LEP is self-contained but integratable into the LEDA software tree. A LEP can be seen as a small software packet which is distributed over a tree structure descending from a root named after the LEP, for example dyn_graph. Descending from this root are the following directories:
We expect that a make command executed in the dyn_graph directory produces the LEP-lib in this directory using the LEDA version referenced from a variable LEDAROOT in the makefile. We want the LEP-libs to be named uniformly as LEP_lep_abbrev, for example LEP_dyn_graph.
The default location for the tree descending from dyn_graph is in the LEPS-directory existing in the LEDA tree top level (just below the normal LEDA root). Extracting it from within LEPS we predefine LEDAROOT to ../../incl which is adaptable in case the LEP is not installed at this default place. For the default installation we additionally provide a make install command (in the Makefile) which should copy the created lib to the standard library place of the global system as well as the header files to a path $LEDAROOT/LEP/lep_abbrev, like $LEDAROOT/LEP/dyn_graph. This should allow include statements like:
#include <LEP/dyn_graph/graph.h>
The LEDA Board consists of Kurt Mehlhorn, Stefan Näher and Christian Uhrig
Contact: leda@mpi-sb.mpg.de
This document was generated using the LaTeX2HTML translator Version 98.1 release (February 19th, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 2 extension.
The translation was initiated by Leda Organisation on 1998-08-17