Prof. Angelika Steger
ETH Zürich
Prof. Dr. Angelika Steger
Institut für Theoretische Informatik
CAB G 37.2
Universitätstrasse 6
8092 Zürich
Phone: +41 44 632 04 97
Fax: +41 44 632 13 99
E-Mail: steger@inf.ethz.ch
Research Interests
- Randomized Algorithms, Probabilistic Methods
- Randomness in Neuroscience
Short CV
1981-85 | Student of mathematics in Freiburg, Heidelberg and Stony Brook |
1985 | Master of Science, SUNY at Stony Brook |
1990 | Ph.D, Universität Bonn |
1994 | Habilitation, Universität Bonn |
1994-95 | Visiting Professor, Universität zu Kiel |
1995-96 | Professor for Discrete Mathematics, Universität Duisburg |
1996-2003 | Professor for Theoretical Computer Science, TU München |
2003- | Professor for Theoretical Computer Science, ETH Zürich |
Awards
1981 | Studienstiftung des Deutschen Volkes
|
1984-85 | Fulbright Scholarship |
1987 | Prize of the Deutsche Gesellschaft für Operations Research (DGOR) for an excellent diploma thesis |
1990 | Prize of Fachbereich Mathematik-Informatik, Universität Bonn, for best dissertation of preceding academic year |
2007 | Member German Academy of Sciences Leopoldina |
2014 | International Congress of Mathematicians ICM'14, invited section talk |
Selected Professional Activities
Publications
Books
- H.J. Prömel, A. Steger
The Steiner Tree Problem. A Tour Through Graphs, Algorithms and Complexity
Vieweg Verlag, Wiesbaden, February 2002, ISBN 3528067624.
Articles in Journals and Refereed Proceedings
2022
2021
2020
- Adaptive tuning curve widths improve sample efficient learning
(joint with F. Meier, R. Dang-Nhu)
Frontiers in Computational Neuroscience, 2020
- A general lower bound for collaborative tree exploration
(joint with Y. Disser, F. Mousset, A. Noever, N. Skoric)
Theoretical Computer Science 811, 2020, 70-78
- An Optimal Decentralized (∆ +1)-Coloring Algorithm
(joint with D. Bertschinger, J. Lengler, A. Martinsson, R. Meier, M. Trujić and E. Welzl)
European Symposium of Algorithms (ESA'20), 2020
2019
- When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
(joint with J. Lengler, A. Martinsson)
In: Analytic Algorithmics and Combinatorics (ANALCO'19), 2019
- Optimal Kronecker-Sum Approximation of Real Time Recurrent Learning
(joint with F. Benzing, M. Gauy, A. Mujika, A. Martinsson)
In: International Conference on Machine Learning (ICML'19), 2019
- The linear hidden subset problem for the (1+1)EA with scheduled and adaptive mutation rates
(joint with H. Einarsson, M. Gauy, J. Lengler, F. Meier, A. Mujika, F. Weissenberger)
Theoretical Computer Science 785, 2019, 150-170
- Resilience of perfect matchings and Hamiltonicity in random graph processes
(joint with R. Nenadov and M. Trujic)
Random Structures & Algorithms 54, 2019, 797-819
- Mutual inhibition with few inhibitory cells via nonlinear inhibitory synaptic interaction
(joint with F. Weissenberger, M. Gauy, X. Zou)
Neural Computation 31, 2019, 2252-2265
- Bootstrap percolation with inhibition
(joint with H. Einarsson, J. Lengler, F. Mousset, K. Panagiotou)
Random Structures & Algorithms 55, 2019, 881-925
2018
- Voltage dependence of synaptic plasticity is essential for rate based learning with short stimuli
(joint with F. Weissenberger, M. Gauy, J. Lengler, F. Meier)
Scientific Reports 8, Article number 4609.
- Drift analysis and evolutionary algorithms revisited
(joint with J. Lengler)
Combinatorics, Probability, and Computing 27, 2018, 643-666.
- Local resilience of an almost spanning k‐cycle in random graphs
(joint with R. Nenadov and M. Trujic)
Random Structures & Algorithms 53, 2018, 728-751.
-
On the origin of lognormal network synchrony in CA1
(joint with F. Weissenberger, H. Einarsson, M. Gauy, J. Lengler, F. Meier, A. Mujika)
Hippocampus 28, 2018, 824-837.
- Even flying cops should think ahead
(joint with A. Martinsson, F. Meier, P. Schnider)
In: Proceedings of 5th International Symposium on Combinatorial Optimization (ISCO'18), LNCS 10856, 2018, 326-337.
- The linear hidden subset problem for the (1+1) EA with scheduled and adaptive mutation rates
(joint with H. Einarsson, M. Gauy, J. Lengler, F. Meier, A. Mujika, F. Weissenberger)
In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'18), ACM, 2018, 1491-1498
- Approximating Real-Time Recurrent Learning with Random Kronecker Factors
(joint with A. Mujika, F. Meier)
In: Proceedings of the 32st Annual Conference on Neural Information Processing Systems (NIPS), 2018
- A hippocampal model for behavioral time acquisition and fast bidirectional replay of spatio-temporal memory sequences
(joint with M. Gauy, J. Lengler, H. Einarsson, F. Meier, F. Weissenberger, M.F. Yanik)
Frontiers in Neuroscience, Systems Biology, 2018.
2017
- A model of fast local homeostatic plasticity
(joint with H. Einarsson, M. Gauy, J. Lengler)
Frontiers in Computational Neuroscience, April 2017.
- Multiassociative Memory: Recurrent Synapses Increase Storage Capacity
(joint with M. Gauy and F. Meier)
Neural Computation 29, 2017, 1375-1405.
- A general lower bound for collaborative tree exploration
(joint with Y. Disser, F. Mousset, A. Noever, N. Skoric)
In: Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2017
- Note on the coefficient of variations of neuronal spike trains
(joint with J. Lengler)
Biological Cybernetics 111, 2017, 229-235.
- Local resilience for squares of almost spanning cycles in sparse random graphs
(joint with A. Noever)
Electronic Journal of Combinatorics 24, 2017, paper #P4.8
- Unique reconstruction threshold for random jigsaw puzzles
(joint with R. Nenadov and P. Pfister)
Chicago Journal of Theoretical Computer Science, 2017, Article 2, pages 1-16
- Long synfire chains emerge by spike-timing dependent plasticity modulated by population activity
(joint with F. Weissenberger, F. Meier, J. Lengler, H. Einarsson)
International Journal of Neural Systems 27, 2017, 1750044 [20 pages].
- Fast-slow recurrent neural networks
(joint with A. Mujika and F. Meier)
In: Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS), 2017
- Symmetric and asymmetric Ramsey properties in random hypergraphs
(joint with L. Gugelmann, R. Nenadov, Y. Person, N. Skoric, H. Thomas)
Forum of Mathematics, Sigma 5, 2017, e28.
- An algorithmic framework for obtaining lower bounds for random Ramsey problems (full version)
(joint with R. Nenadov, Y. Person, N. Skoric)
Journal of Combinatorial Theory, Series B 124, 2017, 1-38.
2016
- A short proof of the Random Ramsey Theorem
(joint with R. Nenadov)
Combinatorics, Probability, and Computing 25, 2016, 130-144.
- Randomness as a Building Block for Reproducibility in Local Cortical Networks
(joint with J. Lengler)
In: Reproducibility: Principles, Practices, Problems, eds. H. Atmanspacher and S. Maasen, Wiley, New York, 2016.
- A polynomial lower bound for distributed graph coloring in a weak LOCAL model
(joint with D. Hefetz, F. Kuhn, Y. Maus)
In: Proceedings of the 30th International Symposium on Distributed Computing (DISC), 2016, 99-113; best paper award.
- Random directed graphs are robustly Hamiltonian
(joint with D. Hefetz and B. Sudakov)
Random Structures & Algorithms 49, 2016, 345-362.
- On the threshold for the Maker-Breaker H-game
(joint with R. Nenadov and M. Stojakovic)
Random Structures & Algorithms 49, 2016, 558-578.
- Connectivity thresholds for bounded size rules
(joint with H. Einarsson, J. Lengler, F. Mousset, K. Panagiotou)
Annals of Applied Probability 26, 2016, 3206-3250.
2015
- Normalization phenomena in asynchronous networks
(joint with A. Karbasi, J. Lengler)
In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP '15), 2015, 688-700.
- An algorithmic framework for obtaining lower bounds for random Ramsey problems
(joint with R. Nenadov, N. Skoric)
In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '15), 2015, 1743-1751.
- The Santa Claus problem in a probabilistic setting
(joint with S. Gerke, K. Panagiotou, J. Schwartz)
Transactions on Algorithms 11, 2015, Article No. 17.
- A dynamic architecture of life
(joint with B. Rubin, J. Brockes, B. Galliot, U. Grossniklaus, D. Lobo, M. Mainardi, M. Mirouze, A. Prochiantz)
F1000Research, 2015, 4:1288.
2014
- A high-capacity model for one shot association learning in the brain
(joint with H. Einarsson, J. Lengler)
Frontiers in Computational Neuroscience, 07 November 2014.
- On the number of graphs without large cliques
(joint with F. Mousset and R. Nenadov)
SIAM J Discrete Mathematics 28, 2014, 1980-1986.
- The determinism of randomness and its use in combinatorics
Proceedings ICM 2014, Vol IV, 2014, 475-488.
- The game chromatic number of dense random graphs
(joint with R. Keusch)
Electronic Journal of Combinatorics 21, 2014, paper #P4.47.
- The maximum degree of random planar graphs
(joint with M. Drmota, O. Giménez, M. Noy, K. Panagiotou)
Proceedings London Mathematical Society 109, 2014, 892-920.
2013
- Explosive percolation in Erdös-Renyi-like random graph processes
(joint with K. Panagiotou, R. Spöhel, H. Thomas)
Combinatorics, Probability, and Computing 22, 2013, 133-145.
- General deletion lemmas via the Harris inequality
(joint with R. Spöhel and L. Warnke)
Journal of Combinatorics 4, 2013, 251-271.
- On the insertion time of cuckoo hashing
(joint with N. Fountoulakis and K. Panagiotou)
SIAM J Computing 42, 2013, 2156-2181.
- Reliable neuronal systems: the importance of heterogeneity
(joint with J. Lengler and F. Jug)
PLOS ONE, December 2013.
2012
- The maximum degree of random planar graphs
(joint with M. Drmota, O. Gimenez, M. Noy, and K. Panagiotou)
In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12), 2012, 281-287.
- Recurrent competitive networks can learn locally excitatory topologies
(joint with F. Jug, M. Cook)
In: Proceedings of the International Joint Conference on Neural Networks (IJCNN '12), 2012, 1-8.
- Extremal subgraphs of random graphs
(joint with G. Brightwell and K. Panagiotou)
Random Structures & Algorithms 41, 2012, 147-178.
- A randomized version of Ramsey's theorem
(joint with L. Gugelmann, Y. Person, H. Thomas)
Random Structures & Algorithms 41, 2012, 488-505.
2011
- On the degree distribution of random planar graphs
(joint with K. Panagiotou)
In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), 2011, 1198-1210.
- Pegging graphs yields a small diameter
(joint with S. Gerke and N. Wormald)
Combinatorics, Probability, and Computing 20, 2011, 239-248.
- Explosive percolation in Erdös-Renyi-like random graph processes (extended abstract)
(joint with K. Panagiotou, R. Spöhel, H. Thomas)
In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb '11), Electronic Notes in Discrete Mathematics 38, 2011, 699-704.
- A randomized version of Ramsey's theorem (extended abstract)
(joint with L. Gugelmann, Y. Person, H. Thomas)
In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb '11), Electronic Notes in Discrete Mathematics 38, 2011, 431-436.
- Interacting maps for fast visual interpretation
(joint with M. Cook, L. Gugelmann, F. Jug, C. Krautz)
In:International Joint Conference on Neural Networks (IJCNN'11), 2011, 770-776.
2010
- Synchrony and asynchrony in neural networks
(joint with F. Kuhn, K. Panagiotou, J. Spencer)
In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), 2010, 949-964.
- Offline thresholds for Ramsey-type games on random graphs
(joint with M. Krivelevich and R. Spöhel)
Random Structures & Algorithms 36, 2010, 57-79.
- Maximal biconnected subgraphs of random planar graphs
(joint with K. Panagiotou)
ACM Transaction of Algorithms 6, 2010, article no. 31; special issue devoted to SODA '09 best papers.
- Coloring the edges of a random graph without a monochromatic giant component
(joint with R. Spöhel and H. Thomas)
Electronic Journal of Combinatorics, 2010, #R133.
- A model of functional recovery after significant loss of neural tissue: biofeedback based healing of vestibular dysfunction
(joint with F. Jug and C. Krautz)
BMC Neuroscience 11, 2010, P111.
- Unsupervised learning of relations
(joint with M. Cook, F. Jug, and C. Krautz)
In: Proceedings of the 20th International Conference on Artificial Neural Networks (ICANN'10), LNCS 6352, Springer-Verlag, 2010, 164-173.
- On properties of random dissections and triangulations
(joint with N. Bernasconi and K. Panagiotou)
Combinatorica 30, 2010, 627-654.
2009
- Maximal biconnected subgraphs of random planar graphs
(joint with K. Panagiotou)
In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), 432-440; full version appeared in ACM Transactions of Algorithms 6, 2010 (invited paper).
- A tight bound on the collection of edges in MSTs of induced subgraphs
(joint with G. Sorkin and R. Zenklusen)
Journal of Combinatorial Theory, Series B 99, 2009, 428-435.
- A quasi-polynomial time approximation scheme for minimum weight triangulation
(joint with J. Remy)
Journal of the ACM 56, 2009, article no. 15; extended abstract appeared in STOC'06.
- Upper bounds for online Ramsey games in random graphs
(joint with Reto Spöhel and M. Marciniszyn)
Combinatorics, Probability, and Computing 18, 2009, 259-270.
- Online Ramsey games in random graphs
(joint with Reto Spöhel and M. Marciniszyn)
Combinatorics, Probability, and Computing 18, 2009, 271-300.
- A note on the chromatic number of a dense random graph
(joint with K. Panagiotou)
Discrete Mathematics 309, 2009, 3420-3423.
- Approximation schemes for node-weighted geometric Steiner tree problems
(joint with J. Remy)
Algorithmica 55, 2009, 240-267; invited for publication in this special issue of APPROX/RANDOM 2005.
- Optimal algorithms for k-search with application in option pricing
(joint with J. Lorenz and K. Panagiotou)
Algorithmica 55, 2009, 311-328; invited for publication in this special issue of ESA 2007.
- Coloring the edges of a random graph without a monochromatic giant component
(joint with Reto Spöhel and Henning Thomas)
Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb'09),
Electronic Notes in Discrete Mathematics 34, 2009, 615-619.
- Asymmetric Ramsey properties of random graphs involving cliques
(joint with M. Marciniszyn, J. Skokan and R. Spöhel)
Random Structures & Algorithms 34, 2009, 419 - 453; extended abstract appeared in RANDOM'06.
- The degree sequence of random graphs from subcritical classes
(joint with N. Bernasconi and K. Panagiotou)
Combinatorics, Probability, and Computing 18, 2009, 647-681; extended abstract appeared in RANDOM'08.
2008
- On properties of random dissections and triangulations
(joint with N. Bernasconi and K. Panagiotou)
In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), 132-141. [full version] appeared in Combinatorica 30, 2010.
- On the degree sequences of random outerplanar and series-parallel graphs
(joint with N. Bernasconi and K. Panagiotou)
In: Proceedings of the 12th International Workshop on Randomized Techniques in Computation (RANDOM'08), LNCS 5171, Springer-Verlag, 2008, 303-316; full version appeared in Combinatorics, Probability, and Computing 18, 2009.
- On the resilience of long cycles in random graphs
(joint with D. Dellamonica Jr., Y. Kohayakawa and M. Marciniszyn)
The Electronic Journal of Combinatorics 15, 2008, R32.
- The random planar graph process
(joint with S. Gerke, D. Schlatter and A. Taraz)
Random Structures and Algorithms 32, 2008, 236-261.
- On the chromatic number of random graphs
(joint with A. Coja-Oghlan and K. Panagiotou)
Journal of Combinatorial Theory, Series B 98, 2008, 980-993; extended abstract appeared in ICALP'07.
2007
- Small subsets inherit sparse ε-regularity
(joint with S. Gerke, Y. Kohayakawa and V. Rödl)
Journal of Combinatorial Theory, Series B 97, 2007, 34-56. [preprint]
- A characterisation for sparse ε-regular pairs
(joint with S. Gerke)
The Electronic Journal of Combinatorics 14, 2007, R4.
- On an online spanning tree problem in randomly weighted graphs
(joint with J. Remy and A. Souza-Offtermatt)
Combinatorics, Probability, and Computing 16, 2007, 127-144.
- K4-free subgraphs of random graphs revisited
(joint with S. Gerke, T. Schickinger, H.J. Prömel and A. Taraz)
Combinatorica 27, 2007, 329-365.
- A probabilistic counting lemma for complete graphs
(joint with S. Gerke and M. Marciniszyn)
Random Structures and Algorithms 31, 2007, 517-534.
- On extremal subgraphs of random graphs
(joint with G. Brightwell and K. Panagiotou)
In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07), 477-485; full version appeared in Random Structures and Algorithms 55, 2009.
- Observational learning in random networks
(joint with J. Lorenz and M. Marciniszyn)
In: Proceedings of the 20th Annual Conference on Learning Theory (COLT '07), 574-588. [preprint full version]
- On the chromatic number of random graphs
(joint with A. Coja-Oghlan and K. Panagiotou)
In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP '07), 777-788; full version appeared in Journal of Combinatorial Theory, Series B 98, 2008.
- Optimal algorithms for k-search with application in option pricing
(joint with J. Lorenz and K. Panagiotou)
In: Proceedings of the 15th Annual European Symposium on Algorithms (ESA '07), 275-286; full version appeared in Algorithmica 55, 2009 (invited paper).
- Random planar graphs with given average degree
(joint with S. Gerke, C. McDiarmid, and A. Weißl)
In: Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh (G.Grimmett, C.McDiarmid, eds.), Oxford University Press, New York, 2007, 83-102. [preprint]
2006
- A new average case analysis for completion time scheduling
(joint with M. Scharbrodt and T. Schickinger)
Journal of the ACM 53, 2006, 121-146.
- Balanced allocation: the heavily loaded case
(joint with P. Berenbrink, A. Czumaj and B. Vöcking)
SIAM Journal on Computing 35, 2006, 1350-1385.
- The expected competitive ratio for weighted completion time scheduling
(joint with A. Souza-Offtermatt)
Theory of Computing Systems 39, 2006, 121-136.
- A quasi-polynomial time approximation scheme for minimum weight triangulation
(joint with J. Remy)
In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC'06), 316-325; full version appeared an Journal of the ACM 56, 2009.
- Random graphs from planar and other addable classes
(joint with C. McDiarmid and D.J.A. Welsh)
In: Topics in Discrete Mathematics, Dedicated to Jarik Nesetril on the occasion of his 60th birthday, Springer-Verlag, 2006, 231-246.
- Threshold functions for asymmetric Ramsey properties involving cliques
(joint with M. Marciniszyn, J. Skokan, R. Spöhel)
In: Proceedings of the 10th International Workshop on Randomized Techniques in Computation (RANDOM'06), LNCS 4110, 2006, 462-474; full version appeared in Random Structures & Algorithms.
2005
- On the evolution of triangle-free graphs
Combinatorics, Probability, and Computing 14, 2005, 211-224.
- Random planar graphs
(joint with C. McDiarmid and D.J.A. Welsh)
Journal of Combinatorial Theory, Series B 93, 2005, 187-205.
- The sparse regularity lemma and its applications
(joint with S. Gerke)
In: Surveys in Combinatorics, 2005, B. Webb, ed., Cambridge University Press, 2005, 227-258.
- Random planar graphs with n nodes and a fixed number of edges
(joint with S. Gerke, C. McDiarmid, and A. Weißl)
In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA'05), 2005, 999-1007.
- Fast algorithms for weighted bipartite matching
(joint with J. Schwartz and A. Weißl)
In: 4th International Workshop on Efficient and Experimental Algorithms (WEA 05), 2005, 476-487.
- The online clique avoidance game on random graphs
(joint with M. Marciniszyn and R. Spöhel)
In: Proceedings of the 9th International Workshop on Randomized Techniques in Computation (RANDOM'05), LNCS 3624, 2005, 390-401.
- Approximation schemes for node-weighted geometric Steiner tree problems
(joint with J. Remy)
In: Proceedings of the 8th Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'05), LNCS 3624, 2005, 221-232; full version appeared in Algorithmica 55, 2009 (invited paper).
- A probabilistic counting lemma for complete graphs
(joint with S. Gerke and M. Marciniszyn)
In: Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EuroComb'05), DMTCS Proceedings Volume AE, 2005, 309-316; full version appeared in Random Structures & Algorithms 31, 2007.
2004
2003
2002
2001
- Asymptotic enumeration, global structure and constrained evolution
(joint with H.J. Prömel and A. Taraz)
Discrete Mathematics 229, 2001, 213-233.
- Counting partial orders with a fixed number of comparable pairs
(joint with H.J. Prömel and A. Taraz)
Combinatorics, Probability and Computing 10, 2001, 159-177.
- Phase transitions in the evolution of partial orders
(joint with H.J. Prömel and A. Taraz)
Journal of Combinatorial Theory, Series A 94, 2001, 230-275.
- Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
(joint with T. Erlebach, P. Rossmanith, H. Stadtherr, and T. Zeugmann)
Theoretical Computer Science 261, 2001, 119-156.
- On the structure of clique-free graphs
(joint with H.J. Prömel and T. Schickinger)
Random Structures and Algorithms 19, 2001, 37-53.
2000
1999
- Approximability of scheduling with fixed jobs (Extended Abstract)
(joint with M. Scharbrodt, H. Weisser)
In: Proceedings of the Tenth ACM-SIAM Symposium on Discrete Algorithms (SODA'99), 1999, 961-962.
Journal version:
- Approximability of scheduling with fixed jobs
(joint with M. Scharbrodt, H. Weisser)
Journal of Scheduling 2, 1999, 267-284.
- Randomized and adversarial load balancing
(joint with P. Berenbrink and T. Friedetzky)
In: Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'99), Springer-Verlag, 1999, pp. 175-184.
- Generating random regular graphs quickly
(joint with N. Wormald)
Combinatorics, Probability and Computing 8, 1999, 377-396.
- Load balancing using bisectors - a tight average-case analysis
(joint with S. Bischof and Th. Schickinger)
In: Proceedings of the Seventh Annual European Symposium on Algorithms (ESA'99), Springer-Verlag, 1999, pp. 172-183.
1998
1997
- RNC-Approximation algorithm for the Steiner Problem
(joint with H.J. Prömel)
In: STACS'97, LNCS 1200, Springer Verlag, 1997, 559-570.©
- Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
(joint with T. Erlebach, P. Rossmanith, H. Stadtherr, and T. Zeugmann)
In: ALT'97, LNCS 1316, Springer Verlag, 1997, 260-276; ©
Journal version was invited for publication in Theoretical Computer Science.
1996
- Counting H-free graphs
(joint with H.J. Prömel)
Discrete Mathematics 154, 1996, 311-315.
- The average number of linear extensions of a partial order
(joint with G. Brightwell and H.J. Prömel)
Journal of Combinatorial Theory, Series A 73, 1996, 193-206.
- On the asymptotic structure of sparse triangle-free graphs
(joint with H.J. Prömel)
Journal of Graph Theory 21, 1996, 137-151.
- Tidier examples for lower bounds on diagonal Ramsey numbers
(joint with C. McDiarmid)
Journal of Combinatorial Theory, Series A 74, 1996, 147-152.
- Wie man Beweise verifizieren kann, ohne sie zu lesen
(joint with H.J. Prömel)
In: Highlights der Informatik (I. Wegener, ed.), Springer Verlag, 1996.©
1995
1994
- Probabilistically checkable proofs and their consequences for approximation algorithms
(joint with S. Hougardy and H.J. Prömel)
Discrete Mathematics 136, 1994, 175-223;
Reprinted in: Trends in Discrete Mathematics (W. Deuber, H.J. Prömel, B. Voigt, eds.), North Holland, 1995.
- Testing hereditary properties efficiently on average
(joint with J. Gustedt)
In: Orders, Algorithms and Applications (V. Bouchitté, M. Morvan, eds.), Proceedings of the International Workshop ORDAL'94, Lyon, LNCS 831, Springer-Verlag, 1994, 100-116.
1993
- Excluding induced subgraphs II: extremal graphs
(joint with H.J. Prömel)
Discrete Applied Mathematics 44, 1993, 283-294.
- A note on induced matchings
(joint with M. Yu)
Discrete Mathematics 120, 1993, 291-295.
- Asymptotic structure of H-free graphs
(joint with H.J. Prömel)
Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference (N. Robertson, P. Seymour, Hrsg.), Contemporary Mathematics 147, American Mathematical Society, 1993, 167-178.
- Extremal graph problems for graphs with a color-critical vertex
(joint with C. Hundack and H.J. Prömel)
Combinatorics, Probability, and Computing 2, 1993, 465-477.
1992
1991
1990
- Globale und lokale Verdrahtungsalgorithmen für Sea-of-Cells Design
(joint with A. Hetzel, B. Korte, R. Krieger, H.J. Prömel and U.D. Radicke)
Informatik - Forschung und Entwicklung 5 (1990), 2-19.
- VLSI-placement based on routing and timing information
(joint with J. Garbers, B. Korte, H.J. Prömel and E. Schwietzke)
Proceedings European Design Automation Conference, 1990, 317-321.
- A design-system for ASIC's with macrocells
(joint with B. Korte and H.J. Prömel)
Proceedings EURO ASIC '90 Conference 1990, 220-224.
- Finding clusters in VLSI circuits
(joint with J. Garbers and H.J. Prömel)
Proceedings International Conference on Computer-Aided-Design, 1990, 520-523.
- Steiner trees in VLSI-layout
(joint with B. Korte and H.J. Prömel)
In: Paths, Flows and VLSI-Layout (B. Korte, L. Lov√°sz, H.J. Prömel, A. Schrijver, eds.), Algorithms and Combinatorics, Vol. 7, Springer Verlag 1990, 185-214.
1989
- Combining partitioning and global routing in sea-of-cells design
(joint with B. Korte and H.J. Prömel)
Proceedings International Conference on Computer-Aided-Design, 1989, 98-101.
1988
- An extension of Karmarkar's algorithm to bounded linear programming problems
Operations Research Proceedings 1987, Springer Verlag 1988, 88-95.
Theses
Master of Science:
An Extension of Karmarkar's Algorithm to Bounded Linear Programming Problems
State University of New York at Stony Brook, August 1985.
Dissertation:
Die Kleitman-Rothschild Methode
Universität Bonn, März 1990.
Habilitationsschrift:
Asymptotic Properties of H-free Graphs
Universität Bonn, November 1993.