Please note: The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Anna Bernasconi

Anna Bernasconi and Bruno Codenotti:

Spectral Analysis of Boolean Functions as a Graph Eigenvalue Problem
In: IEEE Transactions on Computers 48 (1999).

Anna Bernasconi:

On the complexity of balanced Boolean functions
In: Information Processing Letters 70 (1999), pp. 157-163.

Anna Bernasconi, Carsten Damm, Igor Shparlinski:

On the Average Sensitivity of Testing Square-Free Numbers
In: Proceedings of the 5th International Computing and Combinatorics Conference (COCOON'99), LNCS 1627, Springer-Verlag, 1999, pp. 291-299.

Anna Bernasconi, Igor Shparlinski:

Circuit complexity of testing square-free numbers
In: Proceedings of the 16th International Symposium on Theoretical Aspects in Computer Science (STACS'99), LNCS 1563, Springer-Verlag, 1999, pp. 47-56.

Anna Bernasconi, Lavinia Egidi:

Hilbert function and complexity lower bounds for symmetric Boolean functions
In: Information and Computation 153 (1999).

Anna Bernasconi, Bruno Codenotti, Valentino Crespi, Giovanni Resta:

How fast can we compute the permanent of circulant matrices?
In: Linear Algebra and Its Applications 292 1-3 (1999), pp. 15-37.

Anna Bernasconi:

Combinatorial properties of classes of functions hard to compute in constant depth
In: Proceedings of the 4th International Computing and Combinatorics Conference (COCOON'98), LNCS 1449, Springer-Verlag, 1998, pp. 339-348.

Anna Bernasconi:

On the polynomial representation of Boolean functions over GF(2)
In: Proceedings of the 6th Italian Conference on Theoretical Computer Science (ICTCS'98), World Scientific Press, 1998, pp. 265-276.

Anna Bernasconi, Carsten Damm, Igor Shparlinski:

Circuit and Decision Tree Complexity of Some Number Theoretic Problems
Trierer Forschungsberichte Mathematik/Informatik (ISSN 09440488), Bericht Nr. 98-21, Universität Trier, 1998.

Report:

PS-File (177kB)

Anna Bernasconi, Bruno Codenotti:

Introduzione alla Complessità Computazionale
Springer-Verlag Italia. September 1998.

Stefan Bischof

Stefan Bischof, Ralf Ebner, Thomas Erlebach:

Parallel Load Balancing for Problems with Good Bisectors
In: Journal of Parallel and Distributed Computing 60(9), 2000, pp.1047-1073.

Stefan Bischof, Ernst W. Mayr:

On-Line Scheduling of Parallel Jobs with Runtime Restrictions
In: Theoretical Computer Science, Special Issue on On-line Algorithms on the Occasion of OLA'98, to appear.
In: Proceedings of the Ninth Annual International Symposium on Algorithms and Computation, ISAAC'98, LNCS 1533, Springer-Verlag, 1998, pp. 119-128.

Paper:

gzipped PS-File (46kB) (© Springer-Verlag, see also LNCS-homepage)

Technical Report TUM-I9810, SFB Bericht Nr. 342/04/98 A

Report:

PS-File (500kB),

gzipped PS-File (185kB)

Stefan Bischof, Thomas Schickinger, Angelika Steger:

Load Balancing Using Bisectors A Tight Average-Case Analysis
In: Proceedings of the 7th Annual European Symposium on Algorithms, ESA'99, LNCS 1643, Springer-Verlag, 1999, pp. 172-183.

Paper:

gzipped PS-File (53kB) (© Springer-Verlag, see also LNCS-homepage)

Stefan Bischof, Ralf Ebner, Thomas Erlebach:

Parallel Load Balancing for Problems with Good Bisectors
In: Proceedings of the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP'99), IEEE, 1999, pp. 531-538, ISBN 0-7695-0143-5.

Paper:

PDF-File (73kB, only for Computer Society members with an e-account)

Stefan Bischof, Ralf Ebner, Thomas Erlebach:

Load Balancing for Problems with Good Bisectors, and Applications in Finite Element Simulations
In: Proceedings of the 4th International Euro-Par Conference on Parallel Processing, Euro-Par'98, LNCS 1470, Springer-Verlag, 1998, pp. 383-389.

Paper:

gzipped PS-File (40kB) (© Springer-Verlag, see also LNCS-homepage)

In: Tagungsbericht des Workshops "Anwendungsbezogene Lastverteilung" ALV'98, 25.-26. März 1998, München, pp. 1-12. Technischer Bericht TUM-I9806, SFB Bericht Nr. 342/01/98 A (3392kB).

Paper:

gzipped PS-File (58kB)

Technical Report TUM-I9811, SFB Bericht Nr. 342/05/98 A

Report:

PS-File (875kB),

gzipped PS-File (213kB)

Stefan Bischof and Thomas Erlebach:: Classification and Survey of Strategies
In: Dynamic Load Distribution for Parallel Applications (T. Schnekenburger and G. Stellner, eds.), Teubner-Texte zur Informatik, 1997.

Thomas Erlebach

Stefan Bischof, Ralf Ebner, Thomas Erlebach:

Parallel Load Balancing for Problems with Good Bisectors
In: Journal of Parallel and Distributed Computing 60(9), 2000, pp.1047-1073.

Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, Milena Mihail, Pino Persiano:

Optimal wavelength routing on directed fiber trees
In: Theoretical Computer Science (221) 1-2 (1999), pp. 119-137.

Thomas Erlebach:

Scheduling Connections in Fast Networks
Ph.D. Thesis, Technische Universität München, 1999.

Paper:

gzipped PS-File (569kB)

Stefan Bischof, Ralf Ebner, Thomas Erlebach:

Paper:

PDF-File (73kB, only for Computer Society members with an e-account)

Ralf Ebner, Thomas Erlebach, Claudia Gold, Clemens Harlfinger, Roland Wismüller:

A Framework for Recording and Visualizing Event Traces in Parallel Systems with Load Balancing
In: PASA'99 - 5. Workshop Parallele Systeme und Algorithmen, in W. Erhard et al. (Hrsg.): Workshops zur Architektur von Rechensystemen. Berichte zur Rechnerarchitektur, Universität Jena, 1999, pp. 155-162.

Thomas Erlebach:

Maximum Weight Edge-Disjoint Paths in Bidirected Trees
In: Communication and Data Management in Large Networks, Workshop of INFORMATIK'99. Bericht tr-rsfb-99-066, Universität-Gesamthochschule Paderborn, 1999, pp. .13-19.

Thomas Erlebach and Klaus Jansen:

Maximizing the Number of Connections in Optical Tree Networks
In: Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), LNCS 1533, Springer-Verlag, 1998, pp. 179-188.

Stefan Bischof, Ralf Ebner, Thomas Erlebach:

Paper:

gzipped PS-File (40kB) (© Springer-Verlag, see also LNCS-homepage)

In: Tagungsbericht des Workshops "Anwendungsbezogene Lastverteilung" ALV'98, 25.-26. März 1998, München, pp. 1-12. Technischer Bericht TUM-I9806, SFB Bericht Nr. 342/01/98 A (3392kB).

Paper:

gzipped PS-File (58kB)

Technical Report TUM-I9811, SFB Bericht Nr. 342/05/98 A

Report:

PS-File (875kB),

gzipped PS-File (213kB)

Thomas Erlebach and Klaus Jansen:

Off-line and On-line Call-Scheduling in Stars and Trees
Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'97), LNCS 1335, Springer-Verlag, 1997, pp. 199-213.

	Paper:	gzipped PS-File (105kB)
	Slides:	gzipped PS-File (50kB)

Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann:

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
In: ALT'97, LNCS 1316, Springer-Verlag, 1997, pp. 260-276.

Paper:

gzipped PS-File (69kB)

Efficient Learning of One-Variable Pattern Languages from Positive Data
DOI Technical Report DOI-TR-128, Department of Informatics, Kyushu University, Fukuoka, Japan, December 12, 1996.

Report:

PS-File (853kB),

gzipped PS-File (179kB)

Christos Kaklamanis, Pino Persiano, Thomas Erlebach and Klaus Jansen:

Constrained Bipartite Edge Coloring with Applications to Wavelength Routing
Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97), LNCS 1256, Springer-Verlag, 1997, pp. 493-504.

Paper:

gzipped PS-File (50kB)

Thomas Erlebach, Klaus Jansen, Christos Kaklamanis and Pino Persiano:

An Optimal Greedy Algorithm for Wavelength Allocation in Directed Tree Networks
Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location (April 28-30, 1997), AMS, 1998, pp. 117-129.

Paper:

gzipped PS-File (92kB)

Thomas Erlebach and Klaus Jansen:

Call Scheduling in Trees, Rings and Meshes
Proceedings of the 30th Hawaii International Conference on System Sciences (HICSS-30), Vol. 1, IEEE Computer Society Press, 1997, pp. 221-222.

Paper:

gzipped PS-File (13kB)

Thomas Erlebach and Klaus Jansen:

Scheduling of Virtual Connections in Fast Networks
Proceedings of the 4th Parallel Systems and Algorithms Workshop (PASA'96), World Scientific Publishing, 1997, pp. 13-32.

	Paper:	gzipped PS-File (99kB)
	Slides:	gzipped PS-File (68kB)

Stefan Bischof and Thomas Erlebach:

Classification and Survey of Strategies
In: Dynamic Load Distribution for Parallel Applications (T. Schnekenburger and G. Stellner, eds.), Teubner-Texte zur Informatik, 1997.

Tom Friedetzky

Petra Berenbrink, Artur Czumaj, Tom Friedetzky, Nikita Vvedenskaya:

Infinite Parallel Job Allocation
In: Proceedings of the Twelfth ACM Symposium on Parallel Algorithms and Architectures (SPAA 00) , ACM Press, New York, 2000,pp. 99-108.

Petra Berenbrink, Tom Friedetzky and Angelika Steger:: Randomized and Adversarial Load Balancing
In: Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'99), 1999, pp. 175-184.
Petra Berenbrink, Tom Friedetzky and Ernst W. Mayr:: Parallel Continuous Randomized Load Balancing
In: Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'98), 1998, pp. 192-201.

Volker Heun

Volker Heun, Ernst W. Mayr:

Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes
In: Journal of Parallel and Distributed Computing, Vol. 61, No. 8, pp. 1110-1125, 2001.

Paper:

PDF File from Idealibrary.

Volker Heun:

Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen
Fiedr. Vieweg & Sohn Verlagsgesellschaft, Braunschweig/Wiesbaden, 2000.

Volker Heun:

Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices
In: Proceedings of the 7th Annual Symposium on Algorithms (ESA'99), LNCS 1643, Springer-Verlag, 1999, 212-223.

Technical Report ICSI-TR-98-029, International Computer Science Institute (ICSI), Berkeley, 1998.

Report: PS-File (874kB), gzipped PS-File (137kB)

Volker Heun, Ernst W. Mayr:

Efficient Dynamic Embeddings of Arbitrary Binary Trees into Hypercubes
In Proceedings of the 3rd International Workshop on Parallel Algorithms for Irregularly Structured Problems, IRREGULAR'96, LNCS 1117, Springer-Verlag, pp. 287-298.

Technical Report ICSI-TR-98-023, International Computer Science Institute (ICSI), Berkeley, 1998.

Paper: PS-File (907kB), gzipped PS-File (170kB)

Volker Heun, Ernst W. Mayr:

Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes
Technical Report ICSI-TR-98-022, International Computer Science Institute (ICSI), Berkeley, 1998.

Report:

PS-File (646kB),

gzipped PS-File (105kB)

Volker Heun:

Effiziente Einbettungen baumartiger Graphen in den Hyperwürfel
In: Ausgezeichnete Informatikdissertationen 1996, im Auftrag der Gesellschaft für Informatik e.V. herausgegeben durch den Nominierungsausschuß, Teubner-Verlag, 1998, pp. 29-45.

Volker Heun, Wolfgang Merkle and Ulrich Weigand:

Proving the PCP-Theorem
In: Lectures on Proof Verification and Approximation Algorithms (E.W. Mayr, H.-J. Prömel and A. Steger, eds.), LNCS 1367, Springer-Verlag, 1998, pp. 83-160.

Springer offers also an on-line version.

Volker Heun:

Efficient Embeddings of Treelike Graphs into Hypercubes
Ph.D. Thesis, Technische Universität München, 1996
Reihe Informatik, Shaker Verlag, Aachen, 1996

Volker Heun, Ernst W. Mayr:

A General Method for Efficient Embeddings of Graphs into Optimal Hypercubes
In Proceedings of the 2nd International Euro-Par Conference on Parallel Processing, Euro-Par'96, Vol.I, LNCS 1123, Springer-Verlag, pp. 222-233.

Paper:

PS-File (203kB), gzipped PS-File (63kB)

Volker Heun, Ernst W. Mayr:

Optimal Dynamic Edge-Disjoint Embeddings of Complete Binary Trees into Hypercubes
In Proceedings of the 4th Workshop on Parallel Systems and Algorithms, PASA'96, World Scientific Publishing, pp. 195-209.
Technical Report TUM-I9607 (SFB 342/03/96)

Report:

PS-File (473kB),

gzipped PS-File (96kB)

Volker Heun, Ernst W. Mayr:

Embedding Graphs with Bounded Treewidth into Optimal Hypercubes
In Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science STACS'96, LNCS 1046, Springer-Verlag, pp. 157-168.
Technical Report TUM-I9539 (SFB 342/22/95)

Report:

PS-File (975kB),

gzipped PS-File (179kB)

Volker Heun, Ernst W. Mayr:

A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube,
In Journal of Algorithms, Vol.20, No.2 (1996), pp. 375-399,
in Proceedings of the 3rd Workshop on Parallel Systems and Algorithms, PASA'93, (extended abstract),
Mitteilungen - Gesellschaft für Informatik e.V., Parallel-Algorithmen und Rechnerstrukturen, No.11 (1993), pp. 7-11.
Technical Report TUM-I9321

Report:

PS-File (340kB),

gzipped PS-File (87kB)

Klaus Holzapfel

Klaus Holzapfel, Sven Kosub, Moritz Maaß, Hanjo Täubig:

The Complexity of Detecting Fixed-Density Clusters
In: Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC'03)
(May 28-30, 2003, Rome / Italy), vol. 2653 of Lecture Notes in Computer Science, pp. 201-212. Springer-Verlag, Berlin, 2003.

	Abstract
	Reprint:	PDF File (©Springer-Verlag, restricted access).

Klaus Holzapfel, Sven Kosub, Moritz Maaß, Hanjo Täubig:

The complexity of detecting fixed-density clusters
Technischer Bericht TUM-I0212, Dezember 2002.

Paper:

gzipped PS-File (295kB)

Sami Khuri,, Klaus Holzapfel:

EVEGA: An Educational Visualization Environment for Graph Algorithms
In: Proceedings of the 6th Annual Conference on Innovaton and Technology in Computer Science Education (ITiCSE 2001, Canterbury, UK), ACM Press, New York, 2001, pp. 101-104.

Paper:

gzipped PS-File (698kB)

Sami Khuri

Sami Khuri:: Designing Effective Algorithm Visualizations
In: Invited Talk at the Program Visualization Workshop (Joensuu, Finland 07.07.2000-08.07.2000), 2000.
Sami Khuri:, Hsiu_Chin Hsu: Interactive Packages for Learning Image Compression Algorithms
In: 5th Annual Conference on Innovation and Technology in Computer Science Education (Helsinki, Finland 11.07.2000-13.07.2000), ACM Press, New York, 2000, pp. 73-76.
Sami Khuri:, Tom Naps: Interacting with Java-Based Algorithm Visualizations
In: 5th Annual Conference on Innovation and Technology in Computer Science Education, (Helsinki, Finland 11.07.2000-13.07.2000), ACM Press, New York, 2000, .
Sami Khuri, Tim Walters, Yanti Sugono:: A Grouping Genetic Algorithm for Coloring the Edges of Graphs, Evolutionary Computation and Optimization Track
In: Proceedings of 2000 ACM Symposium on Applied Computing (Villa Olmo, Como, Italy, March 19-21, 2000), Carroll, Damiani, Haddad, Oppenheim (Hrsg.), ACM Press, New York, 2000, pp. 422-427.
Sami Khuri, Hsiu-Chin Hsu:: Tools for Visualizing Text Compression Algorithms
In: Proceedings of 2000 ACM Symposium on Applied Computing, Special Track on Computer Uses in Education (Villa Olmo, Como, Italy, March 19-21, 2000), Carroll, Damiani, Haddad, Oppenheim (Hrsg.), ACM Press, New York, 2000, pp. 119-123.
Sami Khuri, Sowmya Miryala:: Genetic Algorithms for Solving Open Shop Scheduling Problems
In: Lecture Notes in Artificial Intelligence; Progress in Artificial Intelligence, Springer Verlag, Berlin, pp. 357-369, September 1999.

Ulla Koppenhagen

Ulla Koppenhagen, Ernst W. Mayr

Optimal Algorithms for the Coverability, the Subword, the Containment, and the Equivalence Problems for Commutative Semigroups
In: Information and Computation 158(2), 2000, pp. 98-124.

Ulla Koppenhagen, Ernst W. Mayr:

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals
In: Journal of Symbolic Computation 28(3), pp. 317-338, 1999.

Ulla Koppenhagen, Ernst W. Mayr:

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals and Applications to Commutative Semigroups
In Proceedings of the Second Magma Conference on Computational Algebra, 1996.

Ulla Koppenhagen, Ernst W. Mayr:

The Complexity of the Coverability, the Containment, and the Equivalence Problems for Commutative Semigroups
In Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (FCT'97), LNCS 1279, Springer-Verlag, 1997.

Ulla Koppenhagen, Ernst W. Mayr:

Optimal Gröbner Base Algorithms for Binomial Ideals
In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96), LNCS 1099, Springer-Verlag, 1996, pp. 244-255.
Technical Report TUM-I9604

Report: PS-File (360kB), gzipped PS-File (104kB)

Ulla Koppenhagen, Ernst W. Mayr:

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals
In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (ISSAC'96), ACM Press, 1996, pp. 55-62.
Technical Report TUM-I9605:

Report: PS-File (408kB), gzipped PS-File (117kB)

Ulla Koppenhagen:

Optimal Algorithms for Binomial Ideals and Commutative Semigroups
Ph.D. Thesis, Technische Universität München, 1997
Reihe Informatik, Shaker Verlag, Aachen, 1997.

Ulla Koppenhagen, Ernst W. Mayr:

The Complexity of the Equivalence Problem for Commutative Semigroups
Technical Report TUM-I9603

Report: PS-File (384kB), gzipped PS-File (112kB)

Ulla Koppenhagen, Ernst W. Mayr:

The Complexity of the Boundedness, Coverability, and Selfcoverability Problems for Commutative Semigroups
Technical Report TUM-I9518

Report: PS-File (294kB), gzipped PS-File (78kB)

Sven Kosub

Matthias Galota, Sven Kosub, Heribert Vollmer:
Generic Separations and Leaf Languages
Technical Report TUM-I0104, September 2001.

Report: gzipped PS-File (96kB)

Klaus Kühnle

Klaus Kühnle:
Space Optimal Computation of Normal Forms of Polynomials
Ph.D. Thesis, Technische Universität München, 1998
Reihe Informatik, Shaker Verlag, Aachen, 1998.

Klaus Kühnle, Ernst W. Mayr:
Exponential space computation of Gröbner bases
(there is also a version for browsers not capable of representing mathematics)
In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (ISSAC'96), ACM Press, 1996, pp. 63-71.
Technical Report TUM-I9606

Report: PS-File (256kB), gzipped PS-File (76kB)

Ernst W. Mayr

Volker Heun, Ernst W. Mayr:
Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes
In: Journal of Parallel and Distributed Computing, Vol. 61, No. 8, pp. 1110-1125, 2001.

Paper: PDF File from Idealibrary.

Ulla Koppenhagen, Ernst W. Mayr
Optimal Algorithms for the Coverability, the Subword, the Containment, and the Equivalence Problems for Commutative Semigroups
In: Information and Computation 158(2), 2000, pp. 98-124.

V.G. Ganzha, Ernst W. Mayr, E.V. Vorozhtsov:
Proceedings of the 2nd International Workshop on Computer Algebra in Scientific Computing, CASC'99
(Müunchen, May 31 -- June 4, 1999) Springer-Verlag, 1999.

Ulla Koppenhagen, Ernst W. Mayr:
An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals
In: Journal of Symbolic Computation 28(3), pp. 317-338, 1999.

Stefan Bischof, Ernst W. Mayr:
On-Line Scheduling of Parallel Jobs with Runtime Restrictions
In: Theoretical Computer Science, Special Issue on On-line Algorithms on the Occasion of OLA'98, to appear.
In: Proceedings of the Ninth Annual International Symposium on Algorithms and Computation, ISAAC'98, LNCS 1533, Springer-Verlag, 1998, pp. 119-128.

Paper: gzipped PS-File (46kB) (© Springer-Verlag, see also LNCS-homepage)

Technical Report TUM-I9810, SFB Bericht Nr. 342/04/98 A

Report: PS-File (500kB), gzipped PS-File (185kB)

Petra Berenbrink, Tom Friedetzky and Ernst W. Mayr:
Parallel Continuous Randomized Load Balancing
In: Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'98), 1998, pp. 192-201.

Volker Heun, Ernst W. Mayr:
Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes
Technical Report ICSI-TR-98-022, International Computer Science Institute (ICSI), Berkeley, 1998.

Report: PS-File (646kB), gzipped PS-File (105kB)

Ulla Koppenhagen, Ernst W. Mayr:
An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals and Applications to Commutative Semigroups
In Proceedings of the Second Magma Conference on Computational Algebra, 1996.

Ernst W. Mayr, Hans-Jürgen Prömel and Angelika Steger (eds.):
Lectures on Proof Verification and Approximation Algorithms
LNCS 1367, Springer-Verlag, 1998.

Springer offers also an on-line version.

Ernst W. Mayr:

Some Complexity Results for Polynomial Ideals
In Journal of Complexity 13, 1997, pp. 303-325.
Technical Report TUM-I9704

Report: PS-File (430kB), gzipped PS-File (186kB)

Slides: PS-File (236kB), gzipped PS-File (68kB)

Andrei Z. Broder, Ernst W. Mayr:
Counting Minimum Weight Spanning Trees
In Journal of Algorithms 24, 1997, pp. 171-176.

Preprint: PS-File (100kB), gzipped PS-File (29kB)

Ernst W. Mayr, Ralph Werchner:
Optimal Tree Contraction and Term Matching on the Hypercube and Related Networks
In Algorithmica 18, 1997, pp. 445-460.
Technical Report TUM-I9532

Report: PS-File (800kB), gzipped PS-File (175kB)

Ulla Koppenhagen, Ernst W. Mayr:
The Complexity of the Coverability, the Containment, and the Equivalence Problems for Commutative Semigroups
In Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (FCT'97), LNCS 1279, Springer-Verlag, 1997.

Ernst W. Mayr:
Parallel Algorithms for Scheduling and Load Balancing
Colloquium AIFB Karlsruhe, 1997.

Slides: PS-File (2046kB), gzipped PS-File (283kB)

F. Hoßfeld, E. Maehle and E.W. Mayr (eds.):
Proceedings of the 4th Workshop on Parallel Systems and Algorithms PASA'96
(Research Center Jülich, Germany, 10-12 April 1996),
World Scientific Publishing, 1997.

Ernst W. Mayr:
Scheduling Interval Orders in Parallel
In Parallel Algorithms and Applications, Vol. 8 (1996), pp. 21-34,
in Proceedings of the Twenty-Eighth Annual Hawaii International Conference on System Sciences, HICSS-28, Vol. II: Software Technology, 1995, pp. 20-28,
Technical Report TUM-I9426

Report: PS-File (333kB), gzipped PS-File (95kB)

Volker Heun, Ernst W. Mayr:
A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube,
In Journal of Algorithms, Vol.20, No.2 (1996), pp. 375-399,
in Proceedings of the 3rd Workshop on Parallel Systems and Algorithms, PASA'93, (extended abstract),
Mitteilungen - Gesellschaft für Informatik e.V., Parallel-Algorithmen und Rechnerstrukturen, No.11 (1993), pp. 7-11.
Technical Report TUM-I9321

Report: PS-File (340kB), gzipped PS-File (87kB)

Ulla Koppenhagen, Ernst W. Mayr:
The Complexity of the Equivalence Problem for Commutative Semigroups
Technical Report TUM-I9603

Report: PS-File (384kB), gzipped PS-File (112kB)

Volker Heun, Ernst W. Mayr:
Embedding Graphs with Bounded Treewidth into Optimal Hypercubes
In Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science STACS'96, LNCS 1046, Springer-Verlag, pp. 157-168.
Technical Report TUM-I9539 (SFB 342/22/95)

Report: PS-File (975kB), gzipped PS-File (179kB)

Volker Heun, Ernst W. Mayr:
Optimal Dynamic Edge-Disjoint Embeddings of Complete Binary Trees into Hypercubes
In Proceedings of the 4th Workshop on Parallel Systems and Algorithms, PASA'96, World Scientific Publishing, pp. 195-209.
Technical Report TUM-I9607 (SFB 342/03/96)

Report: PS-File (473kB), gzipped PS-File (96kB)

Ulla Koppenhagen, Ernst W. Mayr:
Optimal Gröbner Base Algorithms for Binomial Ideals
In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96), LNCS 1099, Springer-Verlag, 1996, pp. 244-255.
Technical Report TUM-I9604

Report: PS-File (360kB), gzipped PS-File (104kB)

Ulla Koppenhagen, Ernst W. Mayr:
An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals
In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (ISSAC'96), ACM Press, 1996, pp. 55-62.
Technical Report TUM-I9605:

Report: PS-File (408kB), gzipped PS-File (117kB)

Klaus Kühnle, Ernst W. Mayr:
Exponential space computation of Gröbner bases
(there is also a version for browsers not capable of representing mathematics)
In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (ISSAC'96), ACM Press, 1996, pp. 63-71.
Technical Report TUM-I9606

Report: PS-File (256kB), gzipped PS-File (76kB)

Ernst W. Mayr, Hans Stadtherr:
Efficient parallel algorithms for scheduling with tree precedence constraints
In Proceedings of the 2nd International Euro-Par Conference on Parallel Processing, Euro-Par'96, LNCS 1124, Springer-Verlag, pp. 543-554.

Volker Heun, Ernst W. Mayr:
A General Method for Efficient Embeddings of Graphs into Optimal Hypercubes In Proceedings of the 2nd International Euro-Par Conference on Parallel Processing, Euro-Par'96, Vol.I, LNCS 1123, Springer-Verlag, pp. 222-233.

Paper: PS-File (203kB), gzipped PS-File (63kB)

Volker Heun, Ernst W. Mayr:
Efficient Dynamic Embeddings of Arbitrary Binary Trees into Hypercubes
In Proceedings of the 3rd International Workshop on Parallel Algorithms for Irregularly Structured Problems, IRREGULAR'96, LNCS 1117, Springer-Verlag, pp. 287-298.
Technical Report ICSI-TR-98-023, International Computer Science Institute (ICSI), Berkeley, 1998.

Paper: PS-File (907kB), gzipped PS-File (170kB)

Ernst W. Mayr, Ralph Werchner:
Divide-and-Conquer Algorithms on the Hypercube
In Theoretical Computer Science, Vol. 162 (1996), pp. 283-296,
in Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS'93, LNCS 665, 1993, pp. 153-162,
Technical Report TUM-I9322

Report: PS-File (485kB), gzipped PS-File (107kB)

Ernst W. Mayr:
Parallel Algorithms for Scheduling and Load Balancing
Department Colloquium Universität Würzburg, 1996.

Slides: PS-File (2046kB), gzipped PS-File (283kB)

Ernst W. Mayr, Hans Stadtherr:
Optimal Parallel Algorithms for Two Processor Scheduling with Tree Precedence Constraints
Technical Report TUM-I9531

Report: PS-File (931kB), gzipped PS-File (187kB)

Ernst W. Mayr:
On Polynominal Ideals, Their Complexity, and Applications
Technical Report TUM-I9520

Report: PS-File (679kB), gzipped PS-File (141kB)

Slides (FCT'95): PS-File (702kB), gzipped PS-File (175kB)

Slides (Tüb '95): PS-File (472kB), gzipped PS-File (80kB)

Ulla Koppenhagen, Ernst W. Mayr:
The Complexity of the Boundedness, Coverability, and Selfcoverability Problems for Commutative Semigroups
Technical Report TUM-I9518

Report: PS-File (294kB), gzipped PS-File (78kB)

Ernst W. Mayr and Claude Puech (eds.):
Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science STACS'95
(Munich, Germany, March 1995),
LNCS 900, Springer-Verlag, 1995.

Ernst W. Mayr:
Algebraic Analysis of Parallel Process Models
Dagstuhl Workshop on Parallel Distributed Algorithms, September 11, 1995.

Slides (Dagstuhl'95): PS-File (634kB), gzipped PS-File (154kB)

Ernst W. Mayr, Gunther Schmidt and Gottfried Tinhofer (eds.):
Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science WG'94
(Herrsching, Germany, June 1994),
LNCS 903, Springer-Verlag, 1995.

P. Enjalbert, E.W. Mayr and K.W. Wagner (eds.):
Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science STACS'94
(Caen, France, February 1994),
LNCS 775, Springer-Verlag, 1994.

Ernst W. Mayr (ed.):
Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science WG'92
(Wiesbaden-Naurod, Germany, June 1992),
LNCS 657, Springer-Verlag, 1993.

Ernst W. Mayr, C. Greg Plaxton:
On the Spanning Trees of Weighted Graphs
In Combinatorica 12, no. 4, 1992, pp. 433-447.

Paper: PS-File (229kB), gzipped PS-File (65kB)

Martin Raab

Martin Raab, Angelika Steger:

Balls into Bins - A Simple and Tight Analysis
In: Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98), LNCS 1518, Springer-Verlag, 1998, pp. 159-170.

Oliver Krone, Martin Raab, Béat Hirsbrunner

Load Balancing For Network Based Multi-threaded Applications.
In: Proceedings of the 5th European PVM/MPI User's Group Meeting (EuroPVM/MPI'98), LNCS 1497, Springer-Verlag, 1998.

Thomas Schickinger

Thomas Schickinger, Angelika Steger:
Diskrete Strukturen (Band 2) - Wahrscheinlichkeitstheorie und Statistik
Springer-Verlag, ISBN 3-540-67599-X , 2001.

Hans Jürgen Prömel,, Thomas Schickinger, Angelika Steger:
On the Structure of Clique-free Graphs
Random Structures and Algorithms 19(1), John Wiley & Sons, 2001, pp. 37-53.

Paper: gzipped PS-File (99kB) (final version © John Wiley & Sons)

Hans Jürgen Prömel,, Thomas Schickinger, Angelika Steger:
A Note on Triangle-Free and Bipartite Graphs
In: special issue of Discrete Mathematics on the occasion of Daniel J. Kleitman's 65th birthday, to appear

Paper: gzipped PS-File (77kB)

Thomas Schickinger, Angelika Steger:
Simplified Witness Tree Arguments
In: Sofsem 2000 Theory and Practice of Informatics LNCS 1963, Springer-Verlag, 2000, pp. 71-87.

Paper: gzipped PS-File (95kB) (© Springer-Verlag, see also LNCS-homepage)

Stefan Bischof, Thomas Schickinger, Angelika Steger:
Load Balancing Using Bisectors A Tight Average-Case Analysis
In: Proceedings of the 7th Annual European Symposium on Algorithms, ESA'99, LNCS 1643, Springer-Verlag, 1999, pp. 172-183.

Paper: gzipped PS-File (53kB) (© Springer-Verlag, see also LNCS-homepage)

Mark Scharbrodt

Mark Scharbrodt, Angelika Steger, Horst Weisser:
Approximability of scheduling with fixed jobs
In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), 1999, pp. 961-962.
In: Journal of Scheduling 2, 1999, pp. 267-284.

Hans Stadtherr

Hans Stadtherr:
Work Efficient Parallel Scheduling Algorithms
Ph.D. Thesis, Technische Universität München, 1998
Utz Verlag, München, 1998.

Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann:
Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
In: ALT'97, LNCS 1316, Springer-Verlag, 1997, pp. 260-276.

Paper: gzipped PS-File (69kB)

Efficient Learning of One-Variable Pattern Languages from Positive Data
DOI Technical Report DOI-TR-128, Department of Informatics, Kyushu University, Fukuoka, Japan, December 12, 1996.

Report: PS-File (853kB), gzipped PS-File (179kB)

Ernst W. Mayr, Hans Stadtherr:
Efficient parallel algorithms for scheduling with tree precedence constraints
In Proceedings of the 2nd International Euro-Par Conference on Parallel Processing, Euro-Par'96, LNCS 1124, Springer-Verlag, pp. 543-554.

Ernst W. Mayr, Hans Stadtherr:
Optimal Parallel Algorithms for Two Processor Scheduling with Tree Precedence Constraints
Technical Report TUM-I9531

Report: PS-File (931kB), gzipped PS-File (187kB)

Angelika Steger

Angelika Steger:
Diskrete Strukturen (Band 1) - Kombinatorik, Graphentheorie, Algebra
Springer-Verlag, ISBN 3-540-67597-3, 2001.

Thomas Schickinger, Angelika Steger:
Diskrete Strukturen (Band 2) - Wahrscheinlichkeitstheorie und Statistik
Springer-Verlag, ISBN 3-540-67599-X , 2001.

Hans Jürgen Prömel,, Thomas Schickinger, Angelika Steger:
On the Structure of Clique-free Graphs
Random Structures and Algorithms 19(1), John Wiley & Sons, 2001, pp. 37-53.

Paper: gzipped PS-File (99kB) (final version © John Wiley & Sons)

Hans Jürgen Prömel,, Thomas Schickinger, Angelika Steger:
A Note on Triangle-Free and Bipartite Graphs
In: special issue of Discrete Mathematics on the occasion of Daniel J. Kleitman's 65th birthday, to appear

Paper: gzipped PS-File (77kB)

Hans-Jürgen Prömel, Angelika Steger:
A new approximation algorithm for the Steiner tree problem with performance ratio 5/3
In: Journal of Algorithms (36), 2000, pp. 89-101.

Thomas Schickinger, Angelika Steger
Simplified Witness Tree Arguments
In: Sofsem 2000 Theory and Practice of Informatics, Hlavac, Vaclav Jeffery, Keith G. Wiedermann, Jiri (Hrsg.), LNCS 1963, Springer-Verlag, 2000, pp. 71-87.

Paper: gzipped PS-File (95kB) (© Springer-Verlag, see also LNCS-homepage)

Petra Berenbrink, Artur Czumaj, Angelika Steger and Berthold Vöcking:
Balanced Allocations: The Heavily Loaded Case
In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'2000), ACM Press, New York, 2000,pp. 745-754.

Stefan Bischof, Thomas Schickinger, Angelika Steger:
Load Balancing Using Bisectors A Tight Average-Case Analysis
In: Proceedings of the 7th Annual European Symposium on Algorithms, ESA'99, LNCS 1643, Springer-Verlag, 1999, pp. 172-183.

Paper: gzipped PS-File (53kB) (© Springer-Verlag, see also LNCS-homepage)

Petra Berenbrink, Tom Friedetzky and Angelika Steger:
Randomized and Adversarial Load Balancing
In: Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'99), 1999, pp. 175-184.

A. Steger and N. Wormald:

Generating random regular graphs quickly
Combinatorics, Probability and Computing 8 (1999) 377-396.

Paper: gzipped PS-File (73kB)

Mark Scharbrodt, Angelika Steger, Horst Weisser:
Approximability of scheduling with fixed jobs
In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), 1999, pp. 961-962.
In: Journal of Scheduling 2, 1999, pp. 267-284.

Martin Raab and Angelika Steger:

Balls into Bins - A Simple and Tight Analysis
In Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98), LNCS 1518, Springer-Verlag, 1998, pp. 159-170.

Y. Kohayakawa, B. Kreuter and Angelika Steger:

An extremal problem for random graphs and the number of graphs with large even-girth
Combinatorica 18, 1998, pp. 101-120.

Paper: gzipped PS-File (73kB)

Hans-Jürgen Prömel, Angelika Steger:
RNC-Approximation Algorithms for the Steiner problem
In STACS'97, LNCS 1200, Springer-Verlag, 1997, pp. 559-570.
Technical Report TUM-I9633

Report: PS-File (172kB), gzipped PS-File (65kB)

Ernst W. Mayr, Hans-Jürgen Prömel and Angelika Steger (eds.):
Lectures on Proof Verification and Approximation Algorithms
LNCS 1367, Springer-Verlag, 1998.

Springer offers also an on-line version.

Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann:
Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
In: ALT'97, LNCS 1316, Springer-Verlag, 1997, pp. 260-276.

Paper: gzipped PS-File (69kB)

Efficient Learning of One-Variable Pattern Languages from Positive Data
DOI Technical Report DOI-TR-128, Department of Informatics, Kyushu University, Fukuoka, Japan, December 12, 1996.

Report: PS-File (853kB), gzipped PS-File (179kB)

Christoph Hundack, Hans-Jürgen Prömel and Angelika Steger:
Extremal graph problems for graphs with a color-critical vertex
In: Combinatorics, geometry and probability. A tribute to Paul Erdös on the occasion of his 80th birthday (Bela Bollobas et al., eds.), Cambridge University Press, 1997, pp. 421-433.

Hans-Jürgen Prömel and Angelika Steger:

Counting H-free graphs
Discrete Mathematics 154,1996, pp. 311-315.

G. Brightwell, Hans-Jürgen Prömel and Angelika Steger:

The average number of linear extensions of a partial order
Journal of Combinatorial Theory, Series A 73,1996, pp. 193-206.

Hans-Jürgen Prömel and Angelika Steger:

On the asymptotic structure of sparse triangle-free graphs
Journal of Graph Theory 21,1996, pp. 137-151.

C. McDiarmid and Angelika Steger:

Tidier examples for lower bounds on diagonal Ramsey numbers
Journal of Combinatorial Theory, Series A 74,1996, pp. 147-152.

Hans-Jürgen Prömel and Angelika Steger:
Wie man Beweise verifiziert, ohne sie zu lesen
In: Highlights der Informatik (I. Wegener, ed.), Springer-Verlag, 1996.

Paper: gzipped PS-File (82kB)

S. Hougardy, Hans-Jürgen Prömel and Angelika Steger:
Probabilistically checkable proofs and their consequences for approximation algorithms
In: Trends in Discrete Mathematics (W. Deuber, H.J. Prömel, B. Voigt, eds.), North Holland, 1995, pp. 175-223.

Hans-Jürgen Prömel and Angelika Steger:

Random l-colorable graphs
Random Structures and Algorithms 6,1995, pp. 21-37.

Lehrstuhl / Chair

Lehrstuhl für Effiziente Algorithmen:
36. Workshop über Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen
Technical Report TUM-I9826

Report: gzipped PS-File (150kB)

Lehrstuhl für Effiziente Algorithmen:
27. Workshop über Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen
Technical Report TUM-I9530

Report: PS-File (263kB) gzipped PS-File (78kB)

Volker Heun, 1993-12-14, 1996-06-20
Tobias Knopff, 1997-03-27
Thomas Erlebach, 1998-12-03

	Report:	PS-File (430kB),	gzipped PS-File (186kB)
	Slides:	PS-File (236kB),	gzipped PS-File (68kB)

Report:	PS-File (679kB),	gzipped PS-File (141kB)
Slides (FCT'95):	PS-File (702kB),	gzipped PS-File (175kB)
Slides (Tüb '95):	PS-File (472kB),	gzipped PS-File (80kB)

Publikationen Publications

Publikationen
Publications