Uni Logo

FORSCHUNGSBERICHT 1999-2001

INDEX
Prev.:Altkatholisches Seminar
Next:Zentrum für Europäische Integrationsforschung (ZEI)/Internationales Wissenschaftsforum Bonn (IWB)
Up:Forschungsbericht
Up:Sonstige Forschungs- und Lehrstätten

Forschungsinstitut für Diskrete Mathematik und Institut für Ökonometrie und Operations Research: Abteilung Operations Research

Allgemeine Angaben:
Lennéstraße 2, 53113 Bonn
Telefon: 0228 / 73-8770
Fax: 0228 / 73-8771
eMail: dm@or.uni-bonn.de
WWW: http://www.or.uni-bonn.de

Hauptamtliche Professoren:
Prof. Dr. Dr. h.c. Bernhard Korte (Direktor)
Prof. Dr. Dr. h.c. László Lovász (Honorarprofessor)
Prof. Dr. Karsten Weihe

Wissenschaftliches Personal:
Universitätsstellen
Dr. Christoph Albrecht
Dipl.-Phys. Sandra Baig
Dipl.-Des. Astrid Blome
Dipl.-Math. Ulrich Brenner
Dr. Traude Castor
Dipl.-Math. Stephan Held
Dipl.-Math. Fritz Jahns
Dr. Bodo Karnbach
Annegret Kehrbaum, M.A.
Dr. Matthias Müller-Hannemann
Dipl.-Inform. Karsten Muuss
Dipl.-Inform. Jörg Nowakovski
Dipl.-Math. Sven Peyer
M.A. Ina Prinz
Dr. Rabe von Randow
Dipl.-Math. André Rohe
Dipl.-Geogr. Sabine Rohe
Dr. Jürgen Schietke
M.A. Anke Schliemann
Dipl.-Inform. Dieta Schülter
Kerstin Schumann, M.A.
Dr. Jörg Seelmann-Eggebert
Dr. Martin Skutella
M.A. Susan Splinter
Dipl.-Math. Christian Szegedy
Dr. Jens Vygen
Dipl.-Math. Jürgen Werber

Stipendiaten
Prof. Dr. Takao Asano
Prof. Dr. William Cook
Prof. Dr. Jean Fonlupt
Prof. Dr. Andras Frank
Prof. Dr. Satoru Fujishige
Dr. Isidoro Gitler
Prof. Dr. Ravi Kannan
Dr. Jorge L. Ramirez Alfonsin
Prof. Dr. Andras Recski
Dr. Zoltan Szigeti
Dr. Martin Zachariasen

Forschungsschwerpunkte:
VLSI-Placement
(Albrecht, Brenner, Schülter, Korte, Vygen)

Potenzial-Balancierungs-Algorithmen
(Albrecht, Cook, Korte, Vygen)

VLSI-Routing
(Albrecht, Korte, Peyer, Rohe, Szegedy, Vygen)

Disjunkte Wege und Multicommodity Flows
(Albrecht, Korte, Recski, Seelmann-Eggebert, Vygen, Werber)

Approximative Algorithmen in der kombinatorischen Optimierung
(Asano, Cook, Korte, Skutella, Vygen)

Parallelisierung von Algorithmen
(Brenner, Muuss, Peyer, Rohe, Schietke, Schülter, Weihe)

Traveling-Salesman-Problem
(Cook, Frank, Korte, Rohe, Vygen)

Perfekte Graphen
(Fonlupt, Lovász, Ramirez Alfonsin)

Minimierung submodularer Funktionen
(Frank, Fujishige, Lovasz, Vygen)

Timing-Optimierung
(Held, Korte, Müller-Hannemann, Muuss, Schietke, Szegedy, Vygen, Werber)

CAD-Systeme für elektrische Schaltanlagen
(Jahns, Karnbach, Nowakovski, Seelmann-Eggebert)

Algebraische Graphentheorie
(Kannan, Lovasz, Szegedy, Szigeti)

Verallgemeinerung matroidaler Strukturen: Greedoide und andere submodulare Systeme
(Korte, Lovász, v. Randow, Recski)

Kürzeste-Wege-Algorithmen in sehr großen Graphen
(Korte, Müller-Hannemann, Peyer, Rohe, Vygen, Weihe)

Optimale Manhattan-Steinerbäume
(Korte, Peyer, Rohe, Vygen, Zachariasen)

Minimum-Cost-Flow-Algorithmen
(Korte, Vygen)

Besondere Forschungsförderung:
"Discrete Optimization: Theory and Applications" (DONET)
(Korte, Vygen, EU-Kommission)

"Training and Mobility of Researchers"
(Korte, EU-Kommission)

Forschungskooperation "Anwendung der diskreten Optimierung in Produktionssteuerung und Schaltanlagenbau"
(Korte, Moeller GmbH)

Forschungskooperation "VLSI-Chip Design"
(Korte, Vygen, IBM Deutschland, IBM USA)

Langzeitprojekt "Diskrete Mathematik und Anwendungen". Arbeitsstelle der Nordrhein-Westfälischen Akademie der Wissenschaften
(Korte, Bund-Länder-Kommission im Rahmen der Konferenz der deutschen Akademien der Wissenschaften)

Veröffentlichungen:

Albrecht, C.
Provably Good Global Routing by a New Approximation Algorithm for Multicommodity Flow
Proceedings of the International Symposium on Physical Design (ISPD), San Diego 2000, pp 19-25.

Albrecht, C.
Global Routing by New Approximation Algorithms for Multicommodity Flow
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2001, pp 622-632.

Albrecht, C.; Korte, B.; Schietke, J.; Vygen, J.
Cycle Time and Slack Optimization for VLSI-Chips
Proceedings of the IEEE International Conference on Computer-Aided Design, 1999, pp 232-238.

Albrecht, C.; Korte, B.; Schietke, J.; Vygen, J.
Maximum Mean Weight Cycle in a Digraph and Minimizing Cycle Time of a Logic Chip
Proceedings of the 1999 Workshop on Discrete Optimization (DO-99), Rutcor, Piscataway 1999, pp 103-128. Discrete Applied Mathematics, Vol. 23 (2002), pp 102-127.

Alon, N.; Fernandez de la Vega, W.; Kannan, R.; Karpinski, M.
Random Sampling and Approximation of MAX-CSP Problems
Proceedings of the 34th annual ACM Symposium on Theory of Computing, 2002, pp 232-239.

Alon, N.; Lovász, L.
Unextendible Product Bases
Journal on Combinatorial Theory A, Vol. 95 (2001), pp 169-179.

Applegate, D.; Cook, W.; Dash, S.; Rohe, A.
Solution of a Min-Max Vehicle Routing Problem
INFORMS Journal on Computing, Vol. 14 (2002), No. 2, pp 132-143.

Applegate, D.; Cook, W.; Rohe, A.
Chained Lin-Kernighan for Large Travelling Salesman Problems
INFORMS Journal on Computing, Vol. 14 (2002), to appear.

A Representation of Ear-Mastroid
Szegedy, Christian
Combinatorica, to appear.

Benczúr, A.; Frank, A.
Covering Symmetric Supermodular Functions by Graphs
Connectivity Augmentation of Networks: Structures and Algorithms, Mathematical Programming Series B, Vol. 84 (1999), No. 3, pp 483-503.

Boros, E.; Recski, A.; Szkaliczki, T.; Wettl, F.
Polynominal Time Manhattan Routing without Doglegs - a Generalization of Gallai´s Algorithm
Computers and Artificial Intelligence, Vol. 18 (1999), pp 403-413.

Brenner, U.; Rohe, A.
An Effective Congestion Driven Placement Framework
Proceedings of the International Symposium on Physical Design (ISPD), ACM, New York 2002, pp 6-11.

Brenner, U.; Vygen, J.
Worst-Case Ratios of Networks in the Rectilinear Plane
Networks, Vol. 38 (2001), pp 126-139.

Brenner, U.; Vygen, J.
Faster Optimal Single-Row Placement with Fixed Ordering
Design, Automation and Test in Europe, IEEE Proceedings (DATE), 2000, pp 117-121.

Chen, F.; Pak, I.; Lovász, L.
Lifting Markov Chains to Speed Up Mixing
Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), 1999, pp 275-281.

Chvátal, V.; Fonlupt, J.; Sun, L.; Zemirline, A.
Recognizing Dart-Free Perfect Graphs
Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). San Francisco, CA, USA, 2000, pp 50-53.

Cook, W.; Dash, S.
On the Matrix-Cut Rank of Polyhedra
Mathematics of Operations Research, Vol. 11 (1999), pp 19-30.

Cook, W.; Rohe, A.
Computing Minimum-Weight Perfect Matchings
INFORMS Journal on Computing, Vol. 11 (1999), pp 138-148.

Drineas, P.; Frieze, A. M.; Kannan, R.; Vempala, S.; Vinay, V.
Clustering in Large Graphs and Matrices
Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999, pp 291-299.

Drineas, P.; Kannan, R.
Fast Monte-Carlo Algorithms for Approximate Matrix Multiplications
Proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS), 2001, pp 452-459.

Faroe, O.; Pisinger, D.; Zachariasen, M.
Local Search for Final Placement in VLSI Design
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2001, pp 565-572.

Feteke, S.; Meijer, H.; Rohe, A.; Tietze, W.
Good and Fast Heuristics for Large Geometric Maximum Matching and Maximum Travelling Salesman Problems
Workshop on Algorithm Engineering and Experiments (ALENEX), 2001, Lecture Notes in Computer Science, Vol. 2153, pp 1-16.

Fonlupt, J.; Mahjoub, A.R.
Critical Extreme Points of the 2-Edge Connected Spanning Subgraph Polytope
7th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 1999, Lecture Notes on Computer Science, Vol. 1610, pp 166-182.

Frank, A.
Finding Minimum Weighted Generator of a Path System
Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future. Vol. 49 (1999), pp 129-138; Journal of Combinatorial Theory B, Vol. 75 (1999), pp 237-244.

Frank, A.
Increasing the Rooted Connectivity of a Digraph by One
Connectivity Augmentation of Networks: Structures and Algorithms, Mathematical Programming Series B, Vol. 84 (1999), No. 3, pp 565-576.

Frank, A.; Jordán, T.
Directed Vertex-Connectivity Augmentation
Connectivity Augmentation of Networks: Structures and Algorithms, Mathematical Programming Series B, Vol. 84 (1999), No. 3, pp 537-553.

Frank, A.; Jordán, T.; Szigeti, Z.
An Orientation Theorem with Parity Conditions
Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 1999, Lecture Notes on Computer Science, Vol. 1610, pp 183-190; Discrete Applied Mathematics, Vol. 115 (2001), pp 37-45.

Frank, A.; Király, Z.
Parity Constrained K-Edge-Connected Orientations
7th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 1999, Lecture Notes on Computer Science, Vol. 1610, pp 183-190.

Frieze, A.M.; Kannan, R.
Quick Approximation to Matrices and Applications
Combinatorica, Vol. 19 (1999), No. 2, pp 175-220.

Gáspár, Z.; Radics, N.; Recski, A.
Rigidity of Square Grids with Holes
Computer-Assisted Mechanics and Engineering Sciences (CAMES), Vol. 6 (1999), pp 329-335.

Iwata, S.; Fleischer, L.; Fujishige, S.
A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions
Journal of the ACM, Vol. 47 (2001), No. 4, pp 761-777.

Kahn, J.; Kim, J.H.; Vu, V.H.; Lovász, L.
The Cover Time, the Blanket Time, and the Matthews Bound
Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2000, pp 467-475.

Kannan, R.; Lovász, L.
Faster Mixing via Average Conductance
Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), 1999, pp 282-287.

Kannan, R.; Tetali, P.; Vempala, S.
Simple Marcov-Chain Algorithms for Generating Bipartite Graphs and Tournaments
Random Structures and Algorithms, Vol. 14 (1999), No. 4, pp 293-308.

Kannan, R.; Vempala, S.; Vetta, A.
On Clusterings - Good, Bad and Spectral
Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2000, pp 367-377.

Kober, C.; Müller-Hannemann, M.
A Case Study in Hexahedral Mesh Generation: Simulation of the Human Mandible
Engineering with Computers (2001), pp 249-260.

Kober, C.; Müller-Hannemann, M.; Sader, R.; Thiele, H., Bauer, H.-J., Zeilhofer, H.-F.; Hoffmann, K.-H.
FEM-Simulation des menschlichen Unterkiefers: Generierung geeigneter Volumengitter
Tagungsband zum 7. Ulm-Workshop (2000), "Die Methode der Finiten Elemente in der Biomechanik, Biomedizin und angrenzenden Gebieten".

Korte, B.; Nesetril
Vojtech Jarnik's Work in Combinatorial Optimization
Discrete Mathematics, Vol 235 (2001), pp 1-17.

Korte, B.; Vygen, J.
Combinatorial Optimization: Theory and Algorithms
Springer, Berlin, 2000, second edition, 2002.

Lipták, L.; Lovász, L.
Facets with Fixed Defect of the Stable Set Polytope
Mathematical Programming, Series A, Vol. 88 (2000), pp 33-44.

Lipták, L.; Lovász, L.
Critical Facets of the Stable Set Polytope
Combinatorica, Vol. 21 (2001), pp 61-88.

Lovász, L.
Hit-And-Run Mixes Fast
Mathematical Programming, Series A, Vol. 86 (1999), pp 443-461.

Lovász, L.
Steinitz Representations of Polyhedra and the Colin de Verdière Number
Journal on Combinatorial Theory B, Vol. 82 (2001), pp 223-236.

Lovász, L.
Integer Sentences and Semidefinite Programming
Publ. Math. Debrecen, Vol. 56 (2000), pp 475-479.

Lovász, L.
Energy of Convex Sets, Shortest Paths, and Resistance
Journal on Combinatorial Theory A, Vol. 94 (2001), pp 363-382.

Lovász, L.
Discrete and Continuous: Two Sides of the same?
Geometric And Functional Analysis (GAFA), Special Volume - GAFA 2000, pp 359-382.

Müller-Hannemann, M.
Shelling Hexahedral Complexes for Mesh Generations in CAD
Journal of Graph Algorithms and Applications, Vol. 5 (2001), No. 5, pp 59-91.

Müller-Hannemann, M.
Drawing Trees, Series-Parallel Digraphs, and Lattices, Chapter 3 in Drawing Graphs
Methods and Models, Lecture Notes in Computer Science Tutorial, Vol. 2025 (2001), pp 46-70.

Müller-Hannemann, M.
Quadrilateral Surface Meshes without Self-Intersecting Dual Cycles for Hexahedral Mesh Generation
Computational Geometry, Theory and Applications, Vol. 22 (2002), pp 75-97.

Müller-Hannemann, M.; Kober, C., Sader, R.; Zeilhofer, H.-F.
Anisotropic Validation of Hexahedral Meshes for Composite Materials in Bioomechanics
Proceedings of the 10th International Meshing Roundtable (2001), pp 249-260.

Müller-Hannemann, M.; Schnee, M.; Weihe, K.
Getting Train Timetables into the Main Storage
Proceedings of Algorithmic Methods and Models for Optimization of Railways (ATMOS), 2002, Electronic Notes in Theoretical Computer Science, Vol.66, No.6.

Müller-Hannemann, M.; Schwartz, A.
Implementing Weighted b-Matching Algorithms: Insights from a Computational Study
ACM Journal of Experimental Algorithmics, Vol. 5 (August 2002).

Müller-Hannemann, M.; Weihe, K.
Pareto Shortest Paths is Often Feasible in Practice
Proceedings of the 5th International Workshop on Algorithm Engineering (WAE) 2001, Lecture Notes in Computer Science, Vol. 2141 (2001), pp 185-197.

Narasimhan, G.; Zachariasen, M.; Zhu, J.
Experiments with Computing Geometric Minimum Spanning Trees
Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments (ALENEX), 2000, pp 183-196.

Nielsen, B.K.; Winter, P.; Zachariasen, M.
On the Location of Steiner Points in Uniformly-Oriented Steiner Trees
Information Processing Letters, Vol. 83 (2002), pp 237-241.

Nielsen, B.K.; Winter, P.; Zachariasen, M.
Rectilinear Trees under Rotation and Related Problems
Proceedings of the 18th European Workshop on Computational Geometry (EWCG), 2002.

Nishizeki, T.; Vygen, J.; Zhou, X.
The Edge-Disjoint Paths Problem is NP-Complete for Series-Parallel Graphs
Proceedings of the 1st Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 1999, pp 103-110; Discrete Applied Mathematics, Vol. 115 (2001), pp 177-186.

Peyer, S.; Zachariasen, M.; Jorgensen, D.G.
Delay-Related Secondary Objectives for Rectilinear Steiner Minimum Trees
Discrete Applied Mathematics, to appear.

Ramirez-Alfonsin, J.; Reed, B.
Perfect Graphs
Wiley, Chichester u.a., 2001.

Recski, A.
Some Polynomially Solvable Subcases of the Detailed Routing Problem in VLSI Design
Discrete Applied Mathematics, Vol. 115 (2001), No. 1-3, pp 199-208.

Recski, A.; Szeszler, D.
3-Dimensional Single Active Layer Routing
Proceedings of the 3rd Japanese Conference on Discrete and Computational Geometry (JCDCG), 2000, Lecture Notes in Computer Science, Vol. 2098, pp 318-329.

Rohe, A.; Zachariasen, M.
Rectilinear Group Steiner Trees and Applications in VLSI Design
Mathematical Programming, to appear.

Sanjeev, A.; Kannan, R.
Learning Mixtures of Arbitrary Gaussians
Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), 2001, pp 247-257.

Schrijver, A.; Lovász, L.
The Colin de Verdière Graph Parameter
Graph Theory and Combinatorial Biology, Bolyai Soc. Math. Stud. 7, pp 29-85.

Schrijver, A.; Lovász, L.
On the Null Space of a Colin de Verdière Matrix
Annales de l'Institute Fourier, Vol. 49, pp 1017-1026.

Szegedy, C.
On the Number of 3-Edge Colorings of Cubic Graphs
European Journal of Combinatorics, Vol. 23 (2002), pp 113-120.

Szigeti, Z.
Hypergraph Connectivity Augmentation
Mathematical Programming, Vol. 84 (1999), pp 519-527.

Szigeti, Z.
An Optimal Ear-Decomposition of Graphs
Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 1999, Lecture Notes on Computer Science, Vol. 1610, pp 415-428.

Szigeti, Z.
On Min-Max Results in Matching Theory
Proceedings of the 6th International Conference on Graph Theory (ICGT), Luminy, 2000, pp 321-324.

Szigeti, Z.
On Generalizations of Matching-Covered Graphs
European Journal of Combinatorics, Vol. 22 (2001), pp 865-877.

Vygen, J.
On Dual Minimum Cost Flow Algorithms
Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing (STOC), 2000, pp 117-125. Mathematical Methods of Operations Research (ZOR), Vol. 56 (2002), pp 101-126.

Vygen, J.
A Note on Schrijver's Submodular Function Minimization Algorithm
Journal of Combinatorial Theory B, to appear.

Warme, D.M.; Winter, P.; Zachariasen, M.
Exact Algorithms for Plane Steiner Tree Problems: A Computational Study
Advances in Steiner Trees, hrg. v. Ding-Zhu Du u.a., Kluwer, Dordrecht, 2000, pp 81-116.

Warme, D.M.; Winter, P.; Zachariasen, M.
Exact Solutions to Large-Scale Plane Steiner Tree Problems
Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999, pp 979-980.

Zachariasen, M.
Rectilinear Full Steiner Tree Generation
Networks, Vol. 33 (1999), pp 125-143.

Zachariasen, M.
Local Search for the Steiner Tree Problem in the Euclidean Plane
European Journal of Operational Research, Vol. 119 (1999), pp 282-300.

Zachariasen, M.
The Rectilinear Steiner Tree Problem: A Tutorial
Steiner Trees in Industries, hrg. v. Ding-Zhu Du u.a., Kluwer, Dordrecht, 2001, pp 467-507.

Zachariasen, M.
A Catalog of Hanan Grid Problems
Networks, Vol. 38 (2001), pp 76-83.

Zachariasen, M.; Winter, P.
Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem
Algorithmica, Vol. 25 (1999), pp 418-437.

Zachariasen, M.; Winter, P.
Obstacle-Avoiding Euclidean Steiner-Trees in the Plane: An Exact Algorithm
Proceedings of the 1st Workshop on Algorithm Engineering and Experimentation (1999), Lecture Notes on Computer Science, Vol. 1619 (1999), pp 282-295.


eMail: Transfer und Öffentlichkeitsarbeit