|
|
 |
|
|
|
|
|
|
|
|
|
| Title: |
|
ABACUS - A Branch And Cut System (->LINK)
(open-source-software)
|
|
|
|
| Abstract: |
|
ABACUS is a software system which
provides a framework for the implementation of
branch-and-bound algorithms using linear
programming relaxations that can be
complemented with the dynamic generation of
cutting planes or columns (branch-and-cut,
branch-and-price, branch-and-cut-and-price).
|
|
|
|
| Software: |
|
The development of ABACUS is
continued as an open source project. See the
project
homepage (->LINK) for further details.
|
|
|
|
| People involved: |
|
,
T. Christof,
M. Elf,
,
,
,
,
,
.
|
|
|
|
| Partners: |
|
|
|
|
|
| Supported by: |
|
,
|
|
|
|
|
|
|
|
|
|
|
| Title: |
|
OGDF - The Open Graph Drawing Framework (->LINK) |
|
|
|
| Abstract: |
|
OGDF, an open source C++ library
of Algorithms for
Graph Drawing, offers a broad range of
existing algorithms for two-dimensional graph
drawing and tools for implementing new
algorithms.
|
|
|
|
| People involved: |
|
, , ,
, , ,
|
|
|
|
| Partners: |
|
|
|
|
|
| Supported by: |
|
German Science Foundation (DFG) |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
AGD - Algorithms for Graph Drawing (->LINK) |
|
|
|
| Abstract: |
|
AGD, a library of Algorithms for
Graph Drawing, offers a broad range of
existing algorithms for two-dimensional graph
drawing and tools for implementing new
algorithms.
|
|
|
|
| People involved: |
|
,
M. Elf, , , , |
|
|
|
| Partners: |
|
|
|
|
|
| Supported by: |
|
European Union: Program IST-1999-14186
ALCOM-FT - ALgorithms and COMplexity - Future
Technology |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
Visualization of Large and Complex Networks (->LINK) |
|
|
|
| Abstract: |
|
The visualization of large and complex networks is indispensable in
order to get a deeper understanding of their structures. The big
challenge is to obtain well-readable layouts in provable
fast running times.
We investigate a general approaches to improve the readability of such drawings
by reducing the number of edge crossings and preserving esthetic
requirements like uniformity of edge length and the display of
symmetries.
|
|
|
|
| People involved: |
|
, |
|
|
|
|
|
|
| Supported by: |
|
European Union |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
Planarization Practices in Automatic Graph Drawing (->LINK) |
|
|
|
| Abstract: |
|
Das Gesamtprojekt ist auf sechs
Jahre angelegt und hat das Ziel, auf
Planarisierungsmethoden beruhende
Zeichenverfahren in ausgewählten
Anwendungsbereichen der Bioinformatik und des
Softwareengineering zur Praxistauglichkeit zu
führen.
|
|
|
|
| People involved: |
|
,
M. Chimani, , ,
, , ,
,
|
|
|
|
| Partners: |
|
|
|
|
|
| Supported by: |
|
German Science Foundation (DFG) |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
IVAN - Interactive Visualization and Analysis of Metabolic Networks (->LINK) |
|
|
|
| Abstract: |
|
Visualization and analysis of metabolic networks has recently been
identified as an important research area. In our interdisciplinary project
we are going to develop a software tool for interactive visualization
and analysis of metabolic networks that takes into account the dynamic
nature of such networks and that effectively supports the biochemist
at work.
|
|
|
|
| People involved: |
|
, , M. Kandyba, A. Menze,
,
,
,
, C.Thelen,
|
|
|
|
|
|
|
| Supported by: |
|
Deutsche Forschungsgemeinschaft
|
|
|
|
|
|
 |
|
|
|
|
|
|
| Title: |
|
Simultaneous Graph Drawing (->LINK) |
|
|
|
| Abstract: |
|
In the visualization process of biochemical networks it
often happens that two or more graphs are dealt with at the same
time. Then the user has to recognize equal substructures in
different graphs which may be drawn in a totally different manner. This project deals with the task to draw equal
substructures in different graphs in the same way. Then the rest of the
graphs are drawn by different aesthetic criteria. The project
covers both theoretical and practical aspects of the problem.
|
|
|
|
| People involved: |
|
,
,
,
,
,
.
|
|
|
|
|
|
|
| Supported by: |
|
Deutsche Forschungsgemeinschaft
|
|
|
|
|
|
|
|
|
|
|
|
|
| Title: |
|
Binary Polynomial Optimization (->LINK) |
|
|
|
| Abstract: |
|
It is an NP-hard problem to optimize a polynomial over binary
variables without further constraints. This is even true in the
quadratic case, where the problem is equivalent to the maximum cut
problem. In our project, we developed a method that allows to make use
of the considerable knowledge on the cut polytope also for the case of
arbitrary degree.
|
|
|
|
| People involved: |
|
,
|
|
|
|
|
|
|
| Supported by: |
|
European Commission (RTN ADONET 504438) |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
Exact Crossing Minimization (->LINK) |
|
|
|
| Abstract: |
|
Finding the crossing number is NP-hard
for general graphs and no practical algorithm for its computation has
been published so far. In our project, we developed an integer linear
programming formulation that is based on a reduction of the general
problem to a restricted version of the crossing number problem in
which each edge may be crossed at most once.
|
|
|
|
| People involved: |
|
,
,
D. Ebner,
,
,
,
,
|
|
|
|
|
|
|
| Supported by: |
|
European Commission (RTN ADONET 504438) |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
Quadratic Optimization over "Easy" Polytopes (->LINK) |
|
|
|
| Abstract: |
|
The problem of optimizing a quadratic objective function over binary
variables subject to linear constraints arises in many
applications. In our project, we focus on problems that could be solved efficiently
if the objective function was linear. For this, we
use the standard linearization and solve the problem with a cutting
plane approach.
|
|
|
|
| People involved: |
|
,
|
|
|
|
|
|
|
| Supported by: |
|
European Commission (RTN ADONET 504438) |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
Crossing Minimization by Quadratic Optimization (->LINK) |
|
|
|
| Abstract: |
|
Many restricted crossing minimization problems are examined in the
literature. They either arise from special applications or from
heuristic simplifications of the general crossing number problem.
Many of these approaches lead to quadratic optimization problems in a
natural way.
|
|
|
|
| People involved: |
|
,
|
|
|
|
|
|
|
| Supported by: |
|
European Commission (RTN ADONET 504438) |
|
|
|
|
|
|
|
|
|
|
| Title: |
|
Computing Exact Ground States of Ising Spin Glasses (->LINK) |
|
|
|
| Abstract: |
|
The physics of spin glasses (e.g. the alloy CuMn), is not yet fully understood. We determine exact ground states of Ising spin glass instances with a branch and cut algorithm and interprete the results physically. |
|
|
|
| People involved: |
|
, |
|
|
|
| Partners: |
|
colleagues
from the spin glass community
|
|
|
|
|
|
|
| Supported by: |
| |
