Project List

GEODUAL is a software for creating and solving geometric instances of the Minimum Spanning Tree problem, the Perfect Matching problem, and the Traveling Salesman problem, along with visual proofs of optimality.

M. Jünger,  M. Schulz, M. Gronemann, W.Zychowicz

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

The development of ABACUS is continued as an open source project. See the ABACUS project homepage for further details.

M. Böhm, T. Christof, M. Elf, C. Gutwenger, M. Jünger, T. Lange, S.Leipert, G. Reinelt, S. Thienel

Universität Heidelberg

European Union, German Science Foundation (DFG)

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.

M. Chimani, C. Gutwenger, M. Jünger, K. Klein, P. Mutzel, M. Schulz

University Dortmund

German Science Foundation (DFG)

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.

C. Buchheim, M. Elf, S. Hachul, M. Jünger, T. Lange, M. Percan

Vienna University of Technology

European Union: Program IST-1999-14186
ALCOM-FT - ALgorithms and COMplexity - Future Technology

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.

S. Hachul, M. Jünger

European Union

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.

C. Buchheim, M. Chimani, C. Gutwenger, M. Jünger, K. Klein, P. Mutzel, M. Percan, M. Schulz, H.-M. Wong

University Dortmund

German Science Foundation (DFG)

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.

C. Buchheim, M. Jünger, M. Kandyba, A. Menze, M. Percan, D. Schomburg, M. Schulz, R. Schunk, C.Thelen, A. Wagner

Deutsche Forschungsgemeinschaft

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.

E. Gassner, M. Jünger, M. Percan, M. Schaefer, M. Schulz,
A. Wagner

Deutsche Forschungsgemeinschaft

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.

C. Buchheim, G. Rinaldi

European Commission (RTN ADONET 504438)

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.

C. Buchheim, M. Chimani, D. Ebner, C. Gutwenger, M. Jünger, G. Klau, P. Mutzel, R. Weiskircher

 European Commission (RTN ADONET 504438)

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.

C. Buchheim, L. Zheng

European Commission (RTN ADONET 504438)

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.

M. Jünger, F. Liers

colleagues from the spin glass community

Deutsche Forschungsgemeinschaft
European Commission (RTN ADONET 504438)

A clustered graph C=(G,T) consists of an undirected graph G and a rooted tree T in which the leaves of T correspond to the vertices of G=(V,E). Each vertex in T corresponds to a subset of the vertices of the graph called ``cluster''. c-planarity is a natural extension of graph planarity for clustered graphs, and plays an important role in automatic graph drawing.

M. Jünger, M. Percan

Vienna University of Technology,
caesar - center of advanced studies and research

European Union: Program IST-1999-14186
ALCOM-FT - ALgorithms and COMplexity - Future Technology

Drawing graphs symmetrically requires to detect abstract symmetries automatically in a first step. This problem is NP-hard for general graphs; we solve it by Branch & Cut.

C. Buchheim, M. Jünger, S.-H. Hong

European Union: Program IST-1999-14186
ALCOM-FT - ALgorithms and COMplexity - Future Technology

FAI is an automated system to install a Debian GNU/Linux operating system on a Linux Cluster without any interaction necessary.

T. Lange

The project team develops mathematical methods and efficient algorithms for automatic graph drawing and provides them in the GoVisual library.

M. Jünger, P. Mutzel, C. Gutwenger, K. Klein, J. Kupke, S. Leipert

Vienna University of Technology,
caesar - center of advanced studies and research

caesar - center of advanced studies and research

The maxcut problem is a prominent combinatorial optimization problem that we solve with a branch and cut algorithm. We focus on but are not restricted to determining maximum cuts in graphs that come from Ising spin glass instances.

M. Jünger, F. Liers

colleagues from the optimization community

Deutsche Forschungsgemeinschaft
European Commission (RTN ADONET 504438)

We compute exact ground states of your spin glass samples: You can send a two- or three-dimensional instance to our server address. The result will be sent back to you.

M. Diehl, M. Jünger, T. Lange, F. Liers