Uni Logo
 

FORSCHUNGSBERICHT 1996-1998


 

Prev.:Altkatholisches Seminar
Next.:Seminar für Orientalische Sprachen
Up:Forschungsbericht
Up:Sonstige Forschungs- und Lehrstätten
Index


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, Telefax: 0228 / 73-8771, eMail: dm@or.uni-bonn.de, WWW: http://www.or.uni-bonn.de

Hauptamtliche Professoren
Prof. Dr. rer.nat. Dr. h.c. Bernhard Korte
Prof. Dr. Dr. h.c. László Lovász (Honorarprofessor)
Prof. Dr. rer.nat. Eberhard Triesch

Wissenschaftliches Personal
Universitätsstellen
Dipl.-Math. Christoph Albrecht
Dipl.-Math. Christopher Anhalt
Dr. Michael Barbulescu
Dr. Asmus Hetzel
Dipl.-Math. Fritz Jahns
Dr. Bodo Karnbach
Annegret Kehrbaum, M.A.
Dipl.-Math. Frank Kruse
Dipl.-Inform. Karsten Muuss
Dipl.-Inform. Jörg Nowakovski
Dr. Gerhard Plaßmann
Dr. Rabe von Randow
Dipl.-Math. André Rohe
Dipl.-Inform. Jürgen Schietke
Dipl.-Inform. Dieta Schülter
Kerstin Schumann, M.A.
Dr. Werner Schwärzler
Dipl.-Inform. Jörg Seelmann-Eggebert
Dipl.-Math. Christian Szegedy
Dr. Jens Vygen

Drittmittelstellen

Stipendiaten
Prof. David Applegate (John v. Neumann - Stiftungsprofessoren d. Stifterverb. f. d. Dt. Wiss.)
Prof. Robert Bixby ()
Prof. Vacek Chvátal ()
Prof. William Cook (John v. Neumann - Sitftungsprofessoren d. Stifterverb. f. d. Dt. Wiss.)
Prof. Jean Fonlupt (John v. Neumann - Stiftungsprofessoren d. Stifterverb. f. d. Dt. Wiss.)
Prof. András Frank ()
Prof. Te C. Hu (John v. Neumann - Stiftungsprofessoren d. Stifterverb. f. d. Dt. Wiss.)
Dr. Martin Klazar ()
Prof. Martin Loebl ()
Prof. Yue Minyi ()
Prof. Kazuo Murota ()
Prof. Jaroslav Nesetril (John v. Neumann - Stiftungsprofessoren d. Stifterverb. f. d. Dt. Wiss.)
Prof. Manfred Padberg (John v. Neumann - Stiftungsprofessoren d. Stifterverb. f. d. Dt. Wiss.)
Prof. Andreas Recski ()
Prof. Bruce Shepherd ()
Dr. Zoltan Szigeti ()

Forschungsschwerpunkte
VLSI-Design
(Albrecht, Hetzel, Korte, Kruse, Muuss, Rohe, Schietke, Schülter, Vygen)

Effiziente Datenstrukturen für Kombinatorische Optimierungsprobleme
(Albrecht, Hetzel, Korte, Muuss, Rohe, Vygen)

Disjunkte Wege und Steinerbäume
(Albrecht, Korte, Seelmann-Eggebert, Vygen)

Approximative Algorithmen für sehr große Travelling Salesman Probleme
(Anhalt, Applegate, Cook, Korte, Rohe)

Polyedrische Kombinatorik
(Applegate, Cook, Lovász, Triesch, Vygen)

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

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

Perfekte Graphen
(Fonlupt, Lovász)

Parallelisierung von Algorithmen
(Hetzel, Schietke, Schülter, Rohe)

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

Submodulare Funktionen
(Korte)

Ramsey Theorie
(Nesetril)

Suchtheorie und partielle Ordnungen
(Triesch)

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

"Human Capital and Mobility"
(Korte, EU-Kommission)

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

Forschungskooperation "VLSI-Chip Design"
(Korte, 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)

Teilprojekt C3 "Methoden und Algorithmen" des SFB 303
(Korte, DFG)

Veröffentlichungen
Applegate D., Bixby R., Chvatal V., Cook W.:
On the solution of travelling salesman problems
Documenta Mathematica: Journal der Deutschen Mathematiker-Vereinigung, ICM III, 645-656, 1998

Applegate D., Jacobson G., Sleator D.:
Computer analysis of sprouts
The Mathematician and Pied Puzzler: A collection in tribute to Martin Gardner (Berlekamp and Rodgers, eds.), A.K. Peters, 199-202, 1999

Applegate D., Reeds J., Scheinberg S., Shepp L., Shor P.:
Some problems in probabilistic tomography
Teoriya Veroyatnosteui i ee Primeneniya 41 (2), 323-335, English translation, Theory of Probability and its Applications 41 (2), 199-209, 1996

Bixby R., Applegate D., Chvatal V., Cook W.:
On the solution of travelling salesman problems
Documenta Mathematica, Journal der Deutschen Mathematiker-Vereinigung, ICM III, 645-656, 1998

Bixby R., Cook W., Cox A., Lee E.K.:
Parallel mixed integer programming
Annals of Operations Research, special issue on parallel computation, 1997

Bixby R., Dennis J.E., Wu Z.:
Solving nonlinear integer programs with a subgradient approach on parallel computers
SIAM News 25, 1997

Bixby R., Lee E.K.Y.:
Solving a truck dispatching scheduling problem using branch-and-cut
Operations Research 46, 355-367, 1998

Cook W., Applegate D., Bixby R., Chvatal V.:
On the solution of travelling salesman problems
Documenta Mathematica: Journal der Deutschen Mathematiker-Vereinigung, ICM III, 645-656, 1998

Cook W., Cunningham W., Pulleyblank W., Schrijver A.:
Combinatorial optimization
John Wiley and Sons, New York, 1997

Cook W., Rohe A.:
Computing minimum-weight perfect matchings
INFORMS Journal of Computing 11, 1999

Cook W.:
Combinatorial optimization
John Wiley and Sons, New York, 1997

Fonlupt J., Mahjoub A.R.:
Critical extreme points of the 2-edge connected spanning subgraph polytope
Proceedings of the 7th IPCO Meeting in Graz (Austria), 1999

Frank A., Erdös P.L., Szekely L.A.:
Minimum multiway cuts in trees
Discrete Applied Mathematics, 87, No. 1-3, 65-76, 1998

Frank A.:
Matroids and submodular functions.
In: Annotated Bibliographies in Combinatorial Optimization, 65-80, 1997

Frank A.:
A survey on T-joins, T-cuts, and convervative weightings
Combinatorics, Paul Erdös is Eighty, Vol 2 (D. Miklos, V.T. Sos, T. Szönyi, eds.) Bolyai Society, Mathematical Studies 2, 213-252, 1996

Frank A.:
Orientations of graphs and submodular flows
Congressus Numerantium 113 (A.J.W. Hilton, ed.) 111-142, 1996

Frank A.:
Applications of relaxed submodularity
Proceedings of the International Congress of Mathematicians, Berlin, Vol. III: Invited Lectures, Documenta Mathematica, Extra Volume ICM (G. Fischer, U. Rehmann, eds.), 345-354, 1998

Frank A.:
Minimum multiway cuts in trees
Discrete Applied Mathematics, 87, No. 1-3, 65-76, 1998

Frank A.:
Finding minimum generators of path system
Journal of Combinatorial Theory, Series B. 75, 237-244, 1999

Hetzel A., Alt M., Stoehr T., Koehl J.:
Analysis, reduction and avoidance of crosstalk on VLSI chips
Proceedings of International Symposium on Physical Design, 211-218, 1998

Hetzel A.:
A sequential detailed router for huge grid graphs
Design, Automation and Test in Europe Conference, 332-338, 1998

Klazar M.:
Extremal functions for sequences
Discrete Mathematics 150, 195-203, 1996

Klazar M.:
On abab-free and abba-free set partitions
European Journal of Combinatorics 17, 53-68, 1996

Klazar M.:
Combinatorial aspects of Davenport-Schinzel sequences
Discrete Mathematics 165/166, 431-445, 1997

Klazar M.:
On well quasiordering of finite languages
Discrete Mathematics 163, 81-88, 1997

Klazar M.:
Twelve countings with rooted plane trees
European Journal of Combinatorics 18, 195-210; Addendum 18, 739-740, 1997

Klazar M.:
On numbers of Davenport-Schinzel sequences
Discrete Mathematics 185, 77-87, 1998

Klazar M.:
On trees and noncrossing partitions
Discrete Applied Mathematics 82, 263-269, 1998

Klazar M.:
Extremal problems for colored trees and Davenport-Schinzel sequences
Discrete Mathematics 197/198, 469-482, 1999

Korte B., Bünnagel U., Vygen J.:
Efficient implementation of the Goldberg-Tarjan minimum-cost flow algorithm
Optimization Methods and Software 10, 157-174, 1998

Minyi Y.:
On the Steiner Problem.
Chinese Journal of Operations Research 16, 71-72, 1996

Murota K, Ikeda K.:
Bifurcation as sources of uncertainties in soil shearing behavior
Soils and Foundations 36, 73-84, 1996

Murota K., Ikeda K., Elishakoff I.:
Reliability of structures subject to normally distributed initial imperfections
Computers and Structures 59, 463-469, 1996

Murota K., Ikeda K., Maruyama K., Yasunami H.:
Uncertainty in the strength of materials and structures
Computers and Structures 67, 71-82, 1998

Murota K., Ikeda K., Yamakawa Y., Yanagisawa E.:
Mode switching and recursive bifurcation in granular materials
Journal of the Mechanics and Physics of Solids 45, 1929-1953, 1997

Murota K., Ikeda K.:
Recursive bifurcation as sources of complexity in soil shearing behavior
Soils and Foundations 37, 17-29, 1997

Murota K., Ikeda K.:
Systematic description of imperfect bifurcation behavior of symmetric systems
International Journal of Solids and Structures 36, 1561-1596, 1998

Murota K., Iwata S., Sakuta I.:
Primal-dual combinatorial relaxation algorithms for the maximum degree of subdeterminants
SIAM Journal on Scientific Computing 17, 993-1012, 1996

Murota K., Iwata S., Shigeno M.:
A fast submodular intersection algorithm for strong map sequences
Mathematics of Operations Research 22, 803-813, 1997

Murota K., Iwata S.:
Horizontal principal structure of layered mixed matrices. Decomposition of discrete systems by design-variable selections
SIAM Journal on Discrete Mathematics 9, 71-86, 1996

Murota K., Scharbroidt M.:
Computing the combinatorial canonical form of a layered mixed matrix
Optimization Methods and Software 10, 373-391, 1998

Murota K.:
Convexity and Steinitz's exchange property
Advances in Mathematics 124, 272-311. Proceedings of the 5th International IPCO Conference Vancouver BC, Canada, June 3-5, 1996 Lecture Notes in Computer Science 1084, 260-274, Springer Verlag, 1996

Murota K.:
Discrete convex analysis
Bulletin of the Japan Society for Industrial and Applied Mathematics 6, 256-269, 1996

Murota K.:
On exchange axioms for valuated matroids and valuated delta-matroids
Combinatorica 6, 591-596, 1996

Murota K.:
Structural approach in systems analysis by mixed matrices - An exposition for index of DAE
ICIAM 95 (Proceedings of the Third International Congress on Industrial and Applied Mathematics held in Hamburg, Germany, July 3-7, 1995 (Kirchgaessner, Mahrenholtz, Mennicken, eds.), Mathematical Research 87, Akademie Verlag, 257-279, 1996

Murota K.:
Two algorithms for valuated delta-matroids
Applied Mathematics Letters 9, 67-71, 1996

Murota K.:
Valuated matroid intersection, I: optimally criteria
SIAM Journal on Discrete Mathematics 9, 545-561, 1996

Murota K.:
Valuated matroid intersection, II: algorithms
SIAM Journal on Discrete Mathematics 9, 562-576, 1996

Murota K.:
Characterizing a valuated delta-matroid as a family of delta-matroids
Journal of Operations Research Society of Japan 40, 565-578, 1997

Murota K.:
Matroid valuation in independent sets
Journal of Combinatorial Theory (B) 69, 59-78, 1997

Murota K.:
Discrete convec analysis
Mathematical Programming 83, 313-371, 1998

Murota K.:
Fenchel-type duality for matroid valuations
Mathematical Programming 82, 357-375, 1998

Nesetril J., Raspaud A., Sopena E.:
Colorings and girth of oriented planar graphs
Discrete Mathematics 165/166, 519-530, 1997

Nesetril J., Sopena E., Vignal L.:
Time preserving homomorphisms of planar graphs
Comment. Math. Univ. Carol. 38, 125-136, 1996

Nesetril J., Turzik D.:
Solving and approximating combinatorial optimization problems (towards MAXCUT and TSP)
Lecture Notes in Computer Science 1338, 70-85, Springer Verlag, 1997

Padberg M, Wilczak M.:
Optimal project selection when borrowing and lending rates differ
Mathematical and Computer Modelling 29, 63-78, 1999

Padberg M., Grötschel M.:
Die optimierte Odyssee
Spektrum der Wissenschaft 4, 75-84, 1999

Padberg M., Rijal M.:
Location, scheduling, design and integer programming
Kluwer Academic Publishers, Boston, 1996

Padberg M., Sung Y.:
An analytical symmetrization of max flow - min cut
Annals of Discrete Mathematics 165/166, 531-545, 1997

Recski A., Balog A., Katona G.O.H., Szasz D.:
European Congress of Mathematicians
Proceedings. Birkhäuser, Basel, 1998

Recski A., Gaspar Z., Radics N.:
Square grids with long diagonals
Optimization Methods and Software 10, 217-231, 1998

Recski A., Nagy G.:
Bar and joint frameworks (in Hungarian)
Matematikai Lapok, 72-75, 1998

Recski A.:
Channel routing in the dogleg-free multilayer Manhatten model
Proceedings of the 1997th European Conference on Circuit Theory and Design, Budapest, I. 39-43, 1997

Recski A.:
Some polynomially solvable subcases of the detailed routing problem in VLSI design
Proceedings of Operations Research Conference, 107-110, Springer Verlag Berlin, 1997

Reed B., Calinescu G., Gomes-Fernandes C.:
Multicuts in unweighted graphs with bounded degree and bounded tree width
Proceedings of IPCO, 1998

Reed B., Cooper C., Frieze A., Molloy M.:
Perfect matchings in random r-regular, s-uniform hypergraphs
Combinatorics, Probability and Computing 5, 1-14, 1996

Reed B., Everett H., Figueiredo C. de, Linhares Sales C., Maffray F., Porto O.:
Path parity and perfection
Discrete Mathematics 165/166, 233-252, 1997

Reed B., Everett H., Klein S.:
An algorithm for finding homogeneous pairs
Discrete Applied Mathematics 72, 209-218, 1997

Reed B., Frieze A.:
Probabilistic analysis of algorithms
Probabilistic Methods in Algorithmic Discrete Mathematics, Springer Verlag Paris, 1998

Reed B., Gasparian S., Markossian M.:
Beta-perfect graphs
Journal of Combinatorial Theory (B) 67, 1-11, 1996

Reed B., Habib M., Mc Diarmid C., Ramirez-Alfonsin J.:
Probabilistic methods in algorithmic discrete mathematics
Springer Verlag Paris, 1998

Reed B., Linhares Sales C., Maffray F.:
On planar perfectly contractive graphs
Graphs and Combinatorics 13, 167-188, 1997

Reed B., Molloy M.:
A bound on the strong chromatic index of a graph
Journal of Combinatorial Theory (B) 69, 103-109, 1997

Reed B., Molloy M.:
Colouring graphs whose chromatic index is close to their maximum degree
Proceedings of LATIN 98, Springer Verlag LNCS 1380, 216-225, 1998

Reed B., Molloy M.:
Further algorithmic aspects of the Local Lemma
Proceedings of STOC, 1998

Reed B., Perkovic L:
Edge colouring regular graphs of high degree
Discrete Mathematics 165/166, 567-578, 1997

Reed B., Robertson N., Seymour P., Thomas R.:
On packing directed circuits
Combinatorica 16, 535-554, 1996

Reed B., Seymour P.:
A fractional approximation to Hadwiger's Conjecture
Journal of Combinatorial Theory (B) 74, 147-152, 1998

Reed B., Shepherd B.:
The Gallai-Younger Conjecture holds for planar graphs
Combinatorica 16, 555-567, 1996

Reed B.:
Tree width and tangles, a new measure of connectivity and some applications
Surveys in Combinatorics (R. Bailey, ed.), Cambridge University Press, Cambridge, 1997

Reed B.:
X, w, and delta (chi, omega and Delta)
Journal of Graph Theory 27, 177-212, 1998

Schietke J., Fassnacht U.:
Timing analysis and optimization of a high-performance CMOS processor chipset.
Design, Automation and Test in Europe Conference, 325-331, 1998

Shepherd B., Gerards A.M.H.:
Strong orientations without even directed circuits
Discrete Mathematics 188, 111-125, 1998

Shepherd B., Gerards A.M.H.:
The graphs with all subraph t-perfect
SIAM Journal of Discrete Mathematics 11, 524-545, 1998

Shepherd B., Kilakos K.:
Excluding minors in cubic graphs
Combinatorics, Computing and Probability 3, 57-78, 1996

Shepherd B., Kilakos K.:
Subdivision and the chromatic index of r-graphs
Journal of Graph Theory 22, 203-211, 1996

Shepherd B., Kilakos K.:
Face extensions in planar cubic graphs
Discrete Mathematics 181, 179-191, 1998

Shepherd B., Lowe E., Walker N.:
Routing and configuration of static path optical transport networks
IEE Electronic Letters 32, 1913-1914, 1996

Shepherd B., Reed B.:
The Gallai-Younger conjecture holds for planar graphs
Combinatorica 16, 555-567, 1996

Szigeti Z., Ageev A., Kostochka A.:
A characterization of seymour graphs
Journal of Graph Theory 24, 357-364, 1997

Szigeti Z., Bang-Jensen J., Gabow H., Jordan T.:
Edge-connectivity augmentation with partition constraints
Proceedings of SODA'98, 1998

Szigeti Z., Cheriyan J., Sebö A.:
An improved approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (Bixby, Rios; eds.), 1998

Szigeti Z.:
On a matroid defined by ear-decompositions of graphs
Combinatorica 16, 233-241, 1996

Szigeti Z.:
On a min-max theorem of cacti
Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (Bixby, Boyd, Rios-Mercado; eds.), 1998

Szigeti Z.:
The two ear theorem on matching covered graphs
Journal of Combinatorial Theory 74, 104-109, 1998

Triesch E., Aigner M.:
Reconstruction problems for digraphs
The Mathematics of Paul Erdös (R.Graham, J.Nesetril; eds.), 43-50, 1996

Triesch E., Nowakovski J., Schwärzler W.:
Using the generalized assignment problem in scheduling the ROSAT space telescope
EJOR 112, 531-541, 1999

Triesch E.:
A group testing problem for hypergraphs of bounded rank
Discrete Applied Mathematics 66, 185-188, 1996

Triesch E.:
Degree sequences of graphs and dominance order
Journal of Graph Theory 22, 89-93, 1996

Triesch E.:
On the recognition complexity of some graph properties
Combinatorica 16, 259-268, 1996

Vygen J., Bünnagel U., Korte B.:
Efficient implementation of the Goldberg-Tarjan minimum-cost flow algorithm
Optimization Methods and Software 10, 157-174, 1998

Vygen J., Nishizeki T., Zhou X.:
The edge-disjoint paths problems is NP-complete for series-parallel graphs
Proceedings of the 1st Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, 103-110, 1999

Vygen J.:
Algorithms for large-scale flat placement
Proceedings of the 34th Design Automation Conference, ACM, 746-751, 1997

Vygen J.:
The two-dimensional weighted median problem
Zeitschrift für Angewandte Mathematik und Mechanik 77, 433-436, 1997

Vygen J.:
Algorithms for detailed placement of standard cells
Design, Automation and Test in Europe, Proceedings, IEEE, 321-324, 1998


Transfer und Öffentlichkeitsarbeit