Publications

2010

Journals

N. Alon, D. Hefetz, M. Krivelevich
Playing to retain the advantage

Combinatorics, Probability and Computing 19(4), 2010, 481-491.

D. Hefetz, T. Mütze, J. Schwartz
On antimagic directed graphs
Journal of Graph Theory 64(3), 2010, 219-232.

M. Krivelevich, R. Spöhel, A. Steger
Offline Thresholds for Ramsey-Type Games on Random Graphs
Random Structures & Algorithms, 36(1), 2010, 57-79.

J. Remy, R. Spöhel, A. Weißl
On Euclidean vehicle routing with allocation
Computational Geometry: Theory and Applications, 43(4), 2010, 357-376.

D. Hefetz, M. Krivelevich, M. Stojakovic, and T. Szabo
Avoider-Enforcer: The rules of the game
J. of Combinatorial Theory Ser. A., 117, 2010, 152-163.

F. Jug, C. Krautz, A.Steger
A model of functional recovery after significant loss of neural tissue: biofeedback based healing of vestibular dysfunction
BMC Neuroscience 11(Suppl 1), 2010, P111.

M. Cook, L. Gugelmann, F. Jug, C. Krautz
Holistically convergent modular networks: a biological principle for recurrent network architecture
BMC Neuroscience 11(Suppl 1), 2010, P38.

D. Hefetz, H. T. T. Tran, A. Saluz
An application of the Combinatorial Nullstellensatz to a graph labeling problem
Journal of Graph Theory, 65, 2010, 70–82.

M. Marciniszyn, R. Spöhel
Online Vertex-Coloring Games in Random Graphs
Combinatorica, 30(1), 2010, 105-123.

R. Spöhel, A. Steger, H. Thomas
Coloring the edges of a random graph without a monochromatic giant component
The Electronic Journal of Combinatorics, 17(1), R133.

N. Bernasconi, K. Panagiotou, A. Steger
On properties of random dissections and triangulations
Combinatorica, 30(6), 2010, 627-654.

Conference Proceedings

M. Cook, F. Jug, C. Krautz, A. Steger
Unsupervised Learning of Relations
In: Lecture Notes in Computer Science (ICANN 2010), 6352, 2010, 164-173.


D. Johannsen, P. Kurur, J. Lengler
Can Quantum Search Accelerate Evolutionary Algorithms?
Genetic and Evolutionary Computation Conference (GECCO) 2010, 1433-1440.

Book Chapters

J. Lengler, B. Mehnert
Random Matrices
In: Matrix Theory, Nova Publisher (to appear).

2009

Journals

G. Sorkin, A. Steger, R. Zenklusen
A tight bound on the collection of edges in MSTs of induced subgraphs
Journal of Combinatorial Theory, Series B 99, 2009, 428-435.

A. Prakash, R. Spöhel, H. Thomas
Balanced Online Ramsey Games in Random Graphs
The Electronic Journal of Combinatorics 16(1), 2009, R11.

D. Hefetz, M. Krivelevich, T. Szabo
Hamilton cycles in highly connected and expanding graphs
Combinatorica, 29(5) (2009), 547-568.

D. Hefetz, M. Krivelevich, M. Stojakovic, T. Szabo
A sharp threshold for the Hamilton cycle Maker-Breaker game
Random Structures & Algorithms 34, 2009, 112-122.

D. Hefetz, M. Krivelevich, M. Stojakovic, T. Szabo
Fast winning strategies in Maker-Breaker games
Journal of Combinatorial Theory, Series B 99, 2009, 39-47.

D. Hefetz, S. Stich
On two problems regarding the Hamilton cycle game
The Electronic Journal of Combinatorics 16(1), 2009, R28.

D. Hefetz, M. Krivelevich, M. Stojakovic, T. Szabo
Fast winning strategies in Avoider-Enforcer games
Graphs and Combinatorics, 25 (2009), 533-544.

M. Marciniszyn, R. Spöhel, A. Steger
Online Ramsey Games in Random Graphs
Combinatorics, Probability and Computing 18(1-2), 2009, 271-300.

M. Marciniszyn, R. Spöhel, A. Steger
Upper Bounds for Online Ramsey Games in Random Graphs
Combinatorics, Probability and Computing 18(1-2), 2009, 259-270.

M. Marciniszyn, J. Skokan, R. Spöhel, A. Steger
Asymmetric Ramsey Properties of Random Graphs Involving Cliques
Random Structures & Algorithms 34(4), 2009, 413-459; extended abstract appeared in RANDOM'06.

M. Cook, F. Jug, C. Krautz
Sharpening Projections
BMC Neuroscience, 10(Suppl 1), 2009, P214.

N. Bernasconi, K. Panagiotou, A. Steger
The Degree Sequence of Random Graphs from Subcritical Classes
Combinatorics, Probability and Computing(5), 2009, 647-681.

J. Remy, A. Steger
Approximation schemes for node-weighted geometric Steiner tree problems
Algorithmica, 55(1), 2009, 240-267.

K. Panagiotou, A. Steger
A note on the chromatic number of a dense random graph
Discrete Mathematics, 309(10), 2009, 3420-3423.

J. Remy, A. Steger
A quasi-polynomial time approximation scheme for minimum weight triangulation
Journal of the ACM, 56(3), 2009.

J. Lorenz, K. Panagiotou, A. Steger
Optimal algorithms for k-search with application in option pricing

Algorithmica, 55(2), 2009, 311-328.

Conference Proceedings

K. Panagiotou, A. Steger
Maximal biconnected subgraphs of random planar graphs
In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09).

R. Spöhel, A. Steger, H.Thomas
Coloring the Edges of a Random Graph Without a Monochromatic Giant Component
In: Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), ENDM 34, 615-619.

2008

Journals

A. Coja-Oghlan, K. Panagiotou, A. Steger
On the chromatic number of random graphs
Journal of Combinatorial Theory, Series B 98, 2008, 980-993; extended abstract appeared in ICALP'07.

D. Dellamonica Jr., Y. Kohayakawa, M. Marciniszyn, A. Steger
On the resilience of long cycles in random graphs
The Electronic Journal of Combinatorics 15, 2008, R32.

D. Hefetz, M. Krivelevich, M. Stojakovic, T. Szabo
Planarity, colorability and minor games
SIAM Journal on Discrete Mathematics, 22(1) (2008) 194-212.

S. Gerke, D. Schlatter, A. Steger, A. Taraz
The random planar graph process
Random Structures & Algorithms 32, 2008, 236-261.

F. Kuhn, R. Wattenhofer, A. Zollinger
An Algorithmic Approach to Geographic Routing in Ad Hoc and Sensor Networks
IEEE/ACM Transactions on Networking 16(1), 2008, 51-62.

Conference Proceedings

J. Schwartz, J. Stuckelberger
Computing Lower Bounds for Steiner Trees in Road Network Design
In: Lecture Notes in Operations Research 8 (ISORA '08), 172-181.

F. Kuhn, T. Locher, S. Schmid
Distributed Computation of the Mode
In: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC '08).

M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, K. Talwar 
Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings
In: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC '08).

N. Bernasconi, K. Panagiotou, A. Steger
On Properties of Random Dissections and Triangulations
In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), 132-141.

T. Muetze, P. Stuedi, F. Kuhn, G. Alonso
Understanding Radio Irregularity in Wireless Networks
In: Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON '08), 82-90.

N. Bernasconi, K. Panagiotou, A.Steger
On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs
In: Proceedings of the 12th Intl. Workshop on Randomization and Computation (RANDOM '08), 303-316.

2007

Journals

J. Remy, A. Souza-Offtermatt, A. Steger
On an online spanning tree problem in randomly weighted graphs
Combinatorics, Probability, and Computing 16 (2007) 127-144.

S. Gerke, M. Marciniszyn, A. Steger
A probabilistic counting lemma for complete graphs
Random Structures & Algorithms (2007), 31 (4), 517-534.

S. Gerke, Y. Kohayakawa, V. Rödl, A. Steger
Small subsets inherit sparse ε-regularity
Journal of Combinatorial Theory, Series B 97 (2007) 34-56.

S.Gerke, A. Steger
A characterization for sparse ε-regular pairs
The Electronic Journal of Combinatorics 14 (2007) R4.

S. Gerke, T. Schickinger, H.J. Prömel, A. Steger, A. Taraz
K4-free subgraphs of random graphs revisited
Combinatorica 27 (2007) 329-365.

D. Mitsche, M. Marciniszyn, M. Stojaković
Online Balanced Graph Avoidance Games
European Journal of Combinatorics (invited to special issue of EuroComb 2005) 28 (2007), 2248-2263.

S. Funke, A. Kesselman, F. Kuhn, Z. Lotker, M. Segal
Improved Approximation Algorithms for Connected Sensor Covers
Wireless Networks 13(2), 2007, 153-164.

R. Almgren, J. Lorenz
Adaptive Arrival Price
Algorithmic Trading III (Spring 2007), 59-66.

Conference Proceedings

J. Lorenz, K. Panagiotou, A. Steger
Optimal Algorithms for k-Search with Application in Option Pricing
In: 15th Annual European Symposium on Algorithms (ESA '07).

I. Abraham, M. Balakrishnan, F. Kuhn, D. Malkhi, V. Ramasubramanian, K. Talwar
Reconstructing Approximate Tree Metrics
In: Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC '07), 43-52.

A. Coja-Oghlan, K. Panagiotou, A. Steger
On the Chromatic Number of Random Graphs
In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP '07), 777-788.

J. Lorenz, M. Marciniszyn, A. Steger
Observational Learning in Random Networks

In: Proceedings of the 20th Annual Conference on Learning Theory (COLT '07), 574-588

F. Kuhn, T. Locher, R. Wattenhofer
Tight Bounds for Distributed Selection (SPAA Best Paper Award)
In: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '07), 145-153.

F. Kuhn, T. Moscibroda
Distributed Approximation of Capacitated Dominating Sets
In: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '07), 161-170.

K. Panagiotou, A. Weißl
Properties of Random Graphs via Boltzmann Samplers
In: International Conference on Analysis of Algorithms (AofA'07).

J. Remy, R. Spöhel, A. Weißl
On Euclidean Vehicle Routing With Allocation
In: Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS '07), LNCS 4619, 601-612.

G. Brightwell, K. Panagiotou, A. Steger
On extremal subgraphs of random graphs
In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07), 477-485.

M. Marciniszyn, R. Spöhel
Online Vertex Colorings of Random Graphs Without Monochromatic Subgraphs
In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07), 486-493.

Conference Proceedings - Invited Contributions

S. Gerke, C. McDiarmid, A. Steger, A. Weißl
Random planar graphs with given average degree
In: Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh (G.Grimmett, C.McDiarmid, eds.), Oxford University Press, New York, 2007, 83-102.

2006

Journals

R. Almgren, J. Lorenz
Optimal Adaptive Trading with Bayesian Updating
Journal of Trading 1(4), 2006, 38-46.

P. Berenbrink, A. Czumaj, A. Steger, B. Vöcking
Balanced allocation: the heavily loaded case
SIAM Journal on Computing 35, 2006, 1350-1385.

M. Scharbrodt, T. Schickinger, A. Steger
A new average case analysis for completion time scheduling
Journal of the ACM 53, 2006, 121-146.

A. Souza, A. Steger
The expected competitive ratio for weighted completion time scheduling
Theory of Computing Systems 39, 2006, 121-136.

S.Gerke, C. Greenhill, N. Wormald
The generalised acyclic edge chromatic number of random regular graphs
Journal of Graph Theory 53, 2006, 101-125.

Conference Proceedings

M. Marciniszyn, J. Skokan, R. Spöhel, A. Steger
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques
In: Proceedings of the 10th. International Workshop on Randomized Techniques in Computation (RANDOM '06), 2006, 462-474.

S. Canzar, J. Remy
Shape Distributions and Protein Similarity.
In: Proceedings of the German Conference on Bioinformatics (GCB '06), 1-10.

K. Panagiotou, A. Souza
On Adequate Performance Measures for Paging
In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC'06), 487-496.

J. Remy, A. Steger
A quasi-polynomial time approximation scheme for minimum weight triangulation
In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC'06), 316-325.

2005

Journals

C. McDiarmid, A. Steger, D.J.A. Welsh
Random planar graphs
Journal of Combinatorial Theory, Series B 93, 2005, 187-205.

A. Steger
On the evolution of triangle-free graphs
Combinatorics, Probability, and Computing 14, 2005, 211-224.

Conference Proceedings

S. Gerke, M. Marciniszyn, A. Steger
A Probabilistic Counting Lemma for Complete Graphs
In: 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings, 2005, 309-316.


S. Gerke, C. McDiarmid, A. Steger, A. Weißl
Random planar graphs with n nodes and a fixed number of edges

In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA'05), 2005, 999-1007.


S. Gerke, A. Steger
The sparse regularity lemma and its applications
In: Surveys in Combinatorics, 2005, B. Webb, ed., Cambridge University Press, 2005, 227-258.


M. Marciniszyn, D. Mitsche, M. Stojaković
Balanced Avoidance Games on Random Graphs
In: 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings, 2005, 329-334.


M. Marciniszyn, R. Spöhel, A. Steger
The Online Clique Avoidance Game on Random Graphs
In: Proceedings of the 9th. International Workshop on Randomized Techniques in Computation (RANDOM '05), 2005, 390 - 401.


J. Remy, A. Steger
Approximation schemes for node-weighted geometric Steiner tree problems
In: Proceedings of the 8th Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'05), 2005, 221-232.


J. Schwartz, A. Steger, A. Weißl
Fast algorithms for weighted bipartite matching
In: 4th International Workshop on Efficient and Experimental Algorithms, WEA 2005, 476-487.

2004

Journals

S.Gerke, C.McDiarmid
On the number of edges in random planar graphs
In: Combinatorics, Probability and Computing 13, 2004, 165-183.

S. Gerke, T. Schickinger, A. Steger
K5-free subgraphs of random graphs
Random Structures and Algorithms 24, 2004, 194-232.

M. Marciniszyn, A. Steger, A. Weißl
E-Jigsaw: Computerunterstützte Rekonstruktion zerrissener Stasi-Unterlagen
Informatik-Spektrum 27, 2004, 248-254. (© Springer-Verlag)

J. Remy
Resource constrained scheduling on multiple machines
Inf. Process. Lett. 91, 2004, 177-182.

Conference Proceedings

A. Souza-Offtermatt, A. Steger
The expected competitive ratio for weighted completion time scheduling
In: Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2004, 620-631.