Algorithms, Structure, Randomness

Publications

• 2008+
• 2007
• 2006
• 2005
• 2004
• 2003
• 2002
• 2001
• 2000

2008+

• Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan Vigerske: Enumeration of Unlabeled Outerplanar Graphs. Submitted.
• Manuel Bodirsky, Omer Gimenez, Mihyun Kang, and Marc Noy: Enumeration and limit laws of series-parallel graphs, European Journal on Combinatorics. Accepted for publication.
• Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random, Theoretical Computer Science. To appear.
• Hans L. Bodlaender, F. van den Eijkhof, and Arie M. C. A. Koster: Safe reduction rules for weighted treewidth, Algorithmica.
• Amin Coja-Oghlan: Solving NP-hard semirandom graph problems in polynomial expected time, Journal of Algorithms. to appear.
• Amin Coja-Oghlan: Coloring semirandom graphs, Combinatorics, Probability and Computing. to appear.
• Mihyun Kang and Taral Guldahl Seierstad: The phase transition of the minimum degree random multi-graph process, Random Structures and Algorithms. accepted for publication.
• Mihyun Kang and Taral Guldahl Seierstad: The critical phase for random graphs with a given degree sequence, Combinatorics, Probability and Computing. accepted for publication.
• Volker Kaibel und Rafael Mechtel: Revlex-Initial 0/1- Polytopes, Journal Combinatorial Theory. to appear.

2007

• Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan Vigerske: An unbiased pointing operator for unlabeled structures, with applications to counting and sampling. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA07), pages 356-365.
• Manuel Bodirsky, Clemens Gröpl, Daniel Johannsen, and Mihyun Kang: A direct decomposition of 3-connected planar graphs, Séminaire Lotharingien de Combinatoire, 54A: Article B54Ak, 15 pp. An earlier version of the paper was presented at the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC05)..
• Manuel Bodirsky, Mihyun Kang, Mike Löffler, and Colin McDiarmid: Random cubic planar graphs, Random Structures and Algorithms, 30: 78-94.
• Amin Coja-Oghlan, Andreas Goerdt, and Andre Lanka: Strong refutation heuristics for random k-SAT, Combinatorics, Probability and Computing, 16: 5-28.

2006

• Manuel Bodirsky and Mihyun Kang: Generating outerplanar graphs uniformly at random, Combinatorics, Probability and Computing, 15(03): 333-343.
• Manuel Bodirsky, Mihyun Kang, and Oleg Verbitsky: On the logical complexity of convex polygon dissections. Archiv der Mathematik.
• H. L. Bodlaender and A. M. C. A. Koster: Safe Separators for Treewidth, Discrete Mathematics, 306(3): 337-350.
• H. L. Bodlaender, T. Wolle, and A. M. C. A. Koster: Contraction and Treewidth Lower Bounds, Journal of Graph Algorithms and Applications, 10(1): 5-49.
• Peter Cameron, Mihyun Kang, and Dudley Stark: Random preorders and alignments. submitted.
• Amin Coja-Oghlan: A spectral heuristic for bisecting random graphs, Random Structures and Algorithms, 29: 351-398.
• Amin Coja-Oghlan: Finding large independent sets in polynomial expected time, Combinatorics, Probability and Computing, 15: 731-751.
• Amin Coja-Oghlan: An adaptive spectral heuristic for partitioning random graphs. In: ICALP, number 4051 in LNCS, pages 691-702. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan, Andreas Goerdt, and Andre Lanka: Spectral partitioning of random graphs with given expected degrees. In: Gonzalo Navarro, Leopoldo Bertossi, and Yoshiharu Kohayakawa (editor): 4th IFIP International Conference on Theoretical Computer Science - TCS 2006 (19th World Computer Congress 2006, Santiago de Chile), pages 271-282.
• Amin Coja-Oghlan, Sven O. Krumke, and Till Nierhoff: A heuristic for the stacker crane problem on trees which is almost surely exact, Journal of Algorithms, 61: 1-19.
• Amin Coja-Oghlan and Lars Kuhtz: An improved algorithm for approximating the chromatic number of G(n,p), Information Processing Letters, 99: 234-238.
• Amin Coja-Oghlan and Andre Lanka: The spectral gap of random graphs with given expected degrees. In: ICALP, number 4051 in LNCS, pages 15-26. Springer.
• Amin Coja-Oghlan, Cristopher Moore, and Vishal Sanwalani: MAX k-CUT and approximating the chromatic number of random graphs, Random Structures and Algorithms, 28: 289-322.
• Benjamin Hiller, Sven O. Krumke, and Jörg Rambau: Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC, Discrete Applied Mathematics, 154(13): 1897-1907. Special Issue for the Latin American Conference on Combinatorics, Graphs and Applications (LACGA 2004).
• R. Hülsermann, M. Jäger, A. M. C. A. Koster, S. Orlowski, R. Wessäly, and A. Zymolka: Availability and Cost Based Evaluation of Demand-wise Shared Protection. In: Proceedings 7th ITG-Workshop on Photonic Networks, pages 161-168, Leipzig, Germany. VDE Verlag GmbH.
• Mihyun Kang, Youngmee Koh, Tomasz Łuczak, and Sangwook Ree: The connectivity threshold for the min-degree random graph process, Random Structures and Algorithms, 29: 105-120.
• Mihyun Kang and Martin Loebl: The enumeration of planar graphs via Wick's theorem, Archiv der Mathematik.
• Arie M. C. A. Koster: Cost-efficient transparent optical networks with high connection availabilities. In: Proceedings 8th International Conference on Transparent Optical Networks, ICTON 2006.
• Arie M. C. A. Koster and A. K. Wagler: On determining the imperfection ratio. In: Proceedings of 5th Cologne-Twente Workshop on Graphs and Combinatorial Optimization.

2005

• Wavelength Assignment in Multifiber WDM Networks. In: Proceedings of INOC 2005, pages 60-66, Lisbon, Portugal. International Network Optimization Conference.
• Manuel Bodirsky: The Core of a Countably Categorical Structure. In: Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS05), volume LNCS 3404, pages 110-120, Stuttgart. Springer.
• Manuel Bodirsky, Omer Gimenez, Mihyun Kang, and Marc Noy: On the number of series-parallel and outerplanar graphs. In: Proceedings of European Conference on Combinatorics, Graph Theory, and Applications (EuroComb05), DMTCS Proceedings Series, pages 383 - 388.
• Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang: Sampling unlabeled biconnected planar graphs. In: Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC05), LNCS 3827, pages 593-603. Springer Verlag.
• Hans L. Bodlaender, F. van den Eijkhof, and Arie M. C. A. Koster: Pre-processing rules for triangulation of probabilistic networks, Computational Intelligence, 21(3): 286-305.
• Hans L. Bodlaender, A. Grigoriev, and Arie M. C. A. Koster: Treewidth Lower Bounds with Brambles. In: G. S. Brodal and S. Leonardi (editor): Proceedings 13th Annual European Symposium on Algorithms, ESA2005, volume 3669 of series Lecture Notes in Computer Science, pages 391-402. Springer.
• Hans L. Bodlaender, Arie M. C. A. Koster, and T. Wolle: Degree-Based Treewidth Lower Bounds. In: Proceedings of 4th International Workshop on Efficient and Experimental Algorithms, WEA 2005, volume 3503 of series Lecture Notes in Computer Science, pages 101-112.
• Amin Coja-Oghlan: The Lovasz number of random graphs, Combinatorics, Probability and Computing, 14: 439-465.
• Amin Coja-Oghlan: On the Laplacian eigenvalues of G(n,p). Preprint.
• Amin Coja-Oghlan, Sven O. Krumke, and Till Nierhoff: A hard dial-a-ride problem that is easy on average, Journal of Scheduling, 8: 197-210.
• Jens Fischer: Enumeration von Hamiltonkreisen. Diplomarbeit, TU Berlin.
• Bernd Gärtner and Volker Kaibel: Two New Bounds for the Random-Edge Simplex Algorithm. ZIB-Report 05-14, ZIB, arXiv: math.CO/0502025, January. 10 pages.
• C. Gruber, Arie M. C. A. Koster, S. Orlowski, S. Orlowski, Roland Wessäly, R. Wessäly, and Adrian Zymolka: Demand-wise Shared Protection revisited: A new model for survivable network design. In: Proceedings of INOC 2005, pages 100-105, Lisbon, Portugal. International Network Optimization Conference.
• C. Gruber, Arie M. C. A. Koster, S. Orlowski, R. Wessäly, and Adrian Zymolka: A Computational Study for Demand-wise Shared Protection. In: Proceedings of DRCN 2005, pages 421-428, Naples, Italy. Design of Reliable Communication Networks.
• I. V. Hicks and E. Kolotoğlu: Branch and Tree Decomposition Techniques for Discrete Optimization. In: J. Cole Smith (editor): TutORials 2005, TutORials in Operations Research Series, chapter 1, pages 1-29. INFORMS Annual Meeting, New Orleans.
• Benjamin Hiller: Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load. technical report ZIB-Report 05-56, ZIB.
• Christoph Hornung: Zählen von Gitter-Triangulierungen in der Ebene. Diplomarbeit, TU Berlin.
• R. Hülsermann, M. Jäger, Arie M. C. A. Koster, and Adrian Zymolka: Demand-wise Shared Protection for Meshed Optical Networks, Journal of Network and Systems Management, 13(1): 35-55.
• Volker Kaibel, Rafael Mechtel, Micha Sharir, and Günter M. Ziegler: The simplex algorithm in dimension three, SIAM Journal on Computing, 34: 475-497.
• Mihyun Kang and Oleg Pikhurko: Maximum K_r+1-free graphs which are not r-partite, Mat. Studii, 24: 12-20.
• A. M. C. A. Koster and A. K. Wagler: Comparing Imperfection Ratio and Imperfection Index for Graph Classes. ZIB-Report 05-50, ZIB.
• Arie M. C. A. Koster and Adrian Zymolka: Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks. In: Proceedings of INOC 2005, pages 44-51, Lisbon, Portugal. International Network Optimization Conference.
• Arie M. C. A. Koster and Adrian Zymolka: On cycles and the stable multi-set polytope, Discrete Optimization, 2(3): 241-255.
• Arie M. C. A. Koster and Adrian Zymolka: Provably Good Solutions for Wavelength Assignment in Optical Networks. In: Proceedings of ONDM 2005, pages 335-345, Milan, Italy. The 9th IFIP Working Conference on Optical Network Design & Modelling.
• Daniela Kühn and Deryk Osthus: Spanning triangulations in graphs, Journal of Graph Theory, 49: 205-233.
• Daniela Kühn and Deryk Osthus: Packings in dense regular graphs, Combinatorics, Probability and Computing, 14: 325-337.
• Daniela Kühn and Deryk Osthus: 4-cycles in graphs without a forbidden even cycle, Journal of Graph Theory, 48: 147-156.
• Carsten Lange and Günter M. Ziegler: On generalized Kneser hypergraph colorings. April. preprint, 8 pages.
• Torsten Schöneborn and Günter M. Ziegler: The Topological Tverberg Problem and winding number, Journal Combinatorial Theory, 112: 82-104.

2004

• Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang: Decomposing, counting, and generating unlabeled cubic planar graphs uniformly at random. Submitted.
• Hans L. Bodlaender and Arie M. C. A. Koster: On the Maximum Cardinality Search Lower Bound for Treewidth. In: Proceedings of International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004).
• Hans L. Bodlaender, Arie M. C. A. Koster, and T. Wolle: Contraction and Treewidth Lower Bounds. In: Proceedings of 12th Annual European Symposium on Algorithms (ESA 2004), volume 3221 of series Lecture Notes in Computer Science, pages 628-639.
• Hans L. Bodlaender, Arie M. C. A. Koster, and T. Wolle: Degree-Based Treewidth Lower Bounds. ZIB-Report 04-44, Zuse Institute Berlin, Berlin.
• Hans L. Bodlaender, Arie M. C. A. Koster, and T. Wolle: A note on Contraction Degeneracy. ZIB-Report 04-43, Zuse Institute Berlin, Berlin.
• Pierce G. Buckley and Deryk Osthus: Popularity based random graph models leading to a scale-free degree sequence, Discrete Mathematics, 282: 53-68.
• Amin Coja-Oghlan: Coloring semirandom graphs optimally. In: Josep Diaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella (editor): Automata, Languages and Programming: 31st International Colloquium (ICALP 2004), volume 3142 of series LNCS, pages 383-395. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan, Andreas Goerdt, Andre Lanka, and Frank Schädlich: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT, Theoretical Computer Science, 329: 1-45.
• Amin Coja-Oghlan and Anusch Taraz: Exact and approximative algorithms for coloring G(n,p), Random Structures and Algorithms, 24(3): 259-278, May.
• D. Hauptmeier, Sven O. Krumke, and Jörg Rambau: The online dial-a-ride problem under reasonable load, Theoretical Computer Science. A preliminary version appeared in the Proceedings of the 4th Italian Conference on Algorithms and Complexity, 2000, vol. 1767 of Lecture Notes in Computer Science.
• Benjamin Hiller: Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem. Diplomarbeit, TU Ilmenau / ZIB.
• Michael Joswig and Günter M. Ziegler: Convex hulls, oracles, and homology, Journal of Symbolic Computation, 38: 1247-1259. special issue for ICMS 2002.
• Volker Kaibel: Low-Dimensional Faces of Random 0/1-Polytopes. In: Daniel Bienstock and Georg L. Nemhauser (editor): Integer Programming and Combinatorial Optimization (IPCO X), number 3064, pages 401-415. Springer.
• Volker Kaibel: On the Expansion of Graphs of 0/1-Polytopes. In: Martin Grötschel (editor): The Sharpest Cut: The Impact of Manfred Padberg and His Work, MPS-SIAM Series on Optimization 4, pages 199-216. A preliminary version appeared as Technical Report at TU Berlin, 2001.
• Mihyun Kang: Random walks on finite graphs with congestion points, Applied Mathematics and Computation, 153: 601-610.
• Mihyun Kang: Efficiency test of pseudorandom number generators using random walks, Journal of Computational and Applied Mathematics, 174(1): 165-177.
• Arie M. C. A. Koster: Wavelength Assignment in Multifiber WDM Networks. In: Proceedings of INOC 2005, Lisbon, Portugal. International Network Optimization Conference.
• Sven O. Krumke, N. Megow, and T. Vredeveld: How to whack moles. In: (editor): In Proceedings of the 1st Workshop on on Approximation and Online Algorithms, volume 2909, pages 192-205. Springer.
• Daniela Kühn and Deryk Osthus: Complete minors in $K_s,s$-free graphs, Combinatorica, 25: 49-61.
• Daniela Kühn and Deryk Osthus: Subdivisions of $K_r+2$ in graphs of average degree at least $r+varepsilon$ and large but constant girth, Combinatorics, Probability and Computing, 13: 361-371.
• Daniela Kühn and Deryk Osthus: Large topological cliques in graphs without a 4-cycle, Combinatorics, Probability and Computing, 13: 93-102.
• Daniela Kühn and Deryk Osthus: Every graph of sufficiently large average degree contains a C_4-free subgraph of large average degree, Combinatorica, 24: 155-162.
• Daniela Kühn and Deryk Osthus: Induced subdivisions in $K_s,s$-free graphs of large average degree, Combinatorica, 24: 287-304.
• Jiří Matoušek and Günter M. Ziegler: Topological lower bounds for the chromatic number: A hierarchy, Jahresbericht der Deutschen Mathematiker-Vereinigung, 106: 71-90.
• Julian Pfeifle and Günter M. Ziegler: On the Monotone Upper Bound Problem, Experimental Mathematics, 13: 1-11.
• Florian Pfender and Günter M. Ziegler: Kissing numbers, sphere packings, and some unexpected proofs, Notices of the AMS, 51(8): 873-883, September.
• Annegret Wagler: The Normal Graph Conjecture is true for Circulants. technical report, ZIB-Report 04-06.
• Annegret Wagler: Relaxing Perfectness: Which Graphs are Almost Perfect?, pages 77-96.

2003

• L. Becchetti, S. Leonardi, Alberto Marchetti-Spaccamela, G. Schäfer, and T. Vredeveld: Average case and smoothed competitive analysis for the multi-level feedback algorithm. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 462-471.
• Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random. In: Proceedings of the Thirtieth International Colloquium on Automata, Languages and Programming (ICALP'03), LNCS 2719, pages 1095-1107. Springer Verlag. Journal version to appear in Theoretical Computer Science.
• Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang: Decomposing, counting, and generating unlabeled cubic planar graphs uniformly at random. In: the European Conference on Combinatorics, Graph Theory, and Applications (EuroComb03), ITI Series 2003-145, pages 61-66. Journal version submitted.
• C. Burch, Robert Carr, Sven O. Krumke, Madhav V. Marathe, C. Phillips, and E. Sundberg: A decomposition-based pseudoapproximation algorithm for network inhibition, pages 51-68. Kluwer Academic Press.
• Amin Coja-Oghlan, Sven O. Krumke, and Till Nierhoff: A heuristic for the stacker crane problem on trees which is almost surely exact. In: Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings, volume 2906 of series LNCS, pages 605-614. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan, Sven O. Krumke, and Till Nierhoff: Scheduling a server on a caterpillar network - a probabilistic analysis. In: Proceedings of the 6th Workshop on Models and Algorithms for Planning and Scheduling Problems, pages 48-50. Available as ZIB-Report 03-12.
• Amin Coja-Oghlan, Sven O. Krumke, and Till Nierhoff: Average case analysis of a hard dial-a-ride-problem. technical report, ZIB-Report 03-12, Konrad-Zuse-Zentrum für Informationstechnik 200.
• Amin Coja-Oghlan, Cristopher Moore, and Vishal Sanwalani: MAX k-CUT and approximating the chromatic number of random graphs. In: J. C. M. Baeten, Jan Karel Lenstra, J. Parrow, and Gerhard J. Woeginger (editor): Automata, Languages and Programming (30th International Colloquium, ICALP 2003), volume 2719 of series LNCS, pages 200-211. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan and Anusch Taraz: Colouring random graphs in polynomial expected time. In: Helmut Alt and M. Habib (editor): STACS 2003, volume 2607 of series LNCS, pages 487-498. Springer. JOURNAL VERSION.
• Volker Kaibel and A. Remshagen: On the graph-density of random 0/1-polytopes. In: Sanjeev Arora, Klaus Jansen, Jose D. P. Rolim, and A. Sahai (editor): Approximation, Randomization, and Combinatorial Optimization (Proc. RANDOM03), number 2764, pages 318-328. Springer.
• Volker Kaibel and Günter M. Ziegler: Counting Lattice Triangulations. In: C. D. Wensley (editor): Surveys in Combinatorics 2003, number http://arxiv.org/abs/math/0211268, pages 277-307. Cambridge University Press.
• Mihyun Kang: First hitting times of simple random walks on graphs with congestion points, International Journal of Mathematics and Mathematical Sciences, 30: 1911-1922.
• Goran Konjevod, Sven O. Krumke, and Madhav V. Marathe: Budget constrained minimum cost connected medians, Journal of Discrete Algorithms. A preliminary version appeared in the Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, 2000, vol. 1928 of Lecture Notes in Computer Science.
• Arie M. C. A. Koster and Adrian Zymolka: Polyhedral investigations on stable multi-sets. technical report, ZIB-Report 03-10.
• Sven O. Krumke, R. Liu, E. L. Lloyd, Madhav V. Marathe, R. Ramanathan, and S. S. Ravi: Topology control problems under symmetric and asymmetric power thresholds. In: In Proceedings of the International Conference on Ad hoc and Wireless Networks, number 2865, pages 187-198. Springer.
• Sven O. Krumke, Madhav V. Marathe, D. Poensgen, S. S. Ravi, and H.-C. Wirth: Budgeted maximum graph coverage. In: Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, number 2573, pages 321-332. Springer.
• Sven O. Krumke, W. E. de Paepe, D. Poensgen, and L. Stougie: News from the online traveling repairman, Theoretical Computer Science, 295(1-3): 279-294. A preliminary version appeared in the Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, 2001, vol. 2136 of Lecture Notes in Computer Science.
• Daniela Kühn and Deryk Osthus: Minors in graphs of large girth, Random Structures and Algorithms, 22: 213-225.
• Daniela Kühn and Deryk Osthus: Partitions of graphs of high minimum degree or connectivity, Journal of Combinatorial Theory (B), 88: 29-43.
• Daniela Kühn and Deryk Osthus: Extremal connectivity for topological cliques in bipartite graphs. submitted.
• J. Marenco and Annegret Wagler: Chromatic Scheduling Polytopes coming from the Bandwidth Allocation Problem in Point-to-Multipoint Radio Access Systems. technical report, ZIB-Report 03-39.
• A. Pêcher and Annegret Wagler: A Construction for Non-Rank Facets of Stable Set Polytopes of Webs. technical report, ZIB-Report 03-21.
• A. Pêcher and Annegret Wagler: On non-rank Facets in Stable Set Polytopes of Webs with Clique Number Four. technical report, ZIB-Report 03-01.
• Hans Jürgen Prömel: Graphentheorie. Spektrum Akademischer Verlag, Heidelberg.
• Hans Jürgen Prömel: Zufällige Graphen. Spektrum Akademischer Verlag, Heidelberg.
• Thomas Voigt and Günter M. Ziegler: Singular 0/1-matrices, and the hyperplanes spanned by random 0/1-vectors. preprint to appear in Combinatorics, Probability & Computing.
• Annegret Wagler: Critical and Anticritical Edges with respect to Perfectness. technical report, ZIB-Report 03-22. submitted to the special issue of Discrete Applied Math. in honor of Claude Berge.

2002

• Ralf Borndörfer: Combinatorial Packing Problems. to appear in: The Sharpest Cut, Festschrift in honor of Manfred Padberg's 60th birthday, MPS/SIAM.
• Amin Coja-Oghlan: Zum Färben k-färbbarer semizufälliger Graphen in erwarteter Polynomzeit mittels Semidefiniter Programmierung. technical report, Bericht Nr. 141 of the Mathematisches Seminar der Universität Hamburg.
• Amin Coja-Oghlan: Coloring k-colorable Semi-Random Graphs in Polynomial Expected Time via Semidefinite Programming. In: Krzystof Diks and W. Rytter (editor): Mathematical Foundations of Computer Science 2002, volume 2420 of series LNCS, pages 201-211. JOURNAL VERSION.
• Amin Coja-Oghlan: Finding sparse induced subgraphs of semirandom graphs. In: Jose D. P. Rolim and S. Vadhan (editor): Randomization and approximation techniques in computer science, volume 2483 of series LNCS, pages 139-148. Springer. JOURNAL VERSION.
• Martin Grötschel and M. Henk: On the Representation of Polyhedra by Polynomial Inequalities. technical report, ZIB-Report 02-15. to appear in: Discrete and Computational Geometry.
• Martin Grötschel, Sven O. Krumke, Jörg Rambau, and L. M. Torres: Making the yellow angels fly: Online dispatching of service vehicles in real time, Siam News, 35(1): 10-11.
• Stefan Hougardy and Annegret Wagler: Perfectness is an Elusive Graph Property. technical report, ZIB-Report 02-11.
• Volker Kaibel, Rafael Mechtel, Micha Sharir, and Günter M. Ziegler: The random edge rule for three-dimensional linear programs. Dec. Preprint, TU Berlin.
• Volker Kaibel and Marc E. Pfetsch: Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences, Comput. Geom., 23: 281-290.
• Arie M. C. A. Koster and Adrian Zymolka: Stable multi-sets, Methods of Operations Research, 56: 45-65.
• Sven O. Krumke: Online Optimization: Competitive Analysis and Beyond. Habilitationsschrift, Technische Universität Berlin.
• Sven O. Krumke, L. Laura, M. Lipmann, Alberto Marchetti-Spaccamela, W. E. de Paepe, D. Poensgen, and L. Stougie: Non-abusiveness helps: An O(1)-competitive algorithm for minimizing the maximum time in the online traveling salesman problem. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, number 2462, pages 200-214. Springer.
• Sven O. Krumke, M. Lipmann, W. E. de Paepe, D. Poensgen, Jörg Rambau, L. Stougie, and Gerhard J. Woeginger: How to cut a cake almost fairly. to appaer in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms.
• Sven O. Krumke and D. Poensgen: Online call admission in optical networks with larger wavelength demands. In: Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, number 2573, pages 333-344. Springer.
• Sven O. Krumke and Jörg Rambau: Probieren geht über Studieren? Entscheidungshilfen für kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik, at - Automatisierungstechnik, 12: 568-575.
• Sven O. Krumke, Jörg Rambau, and L. M. Torres: Real-time dispatching of guided and unguided automobile service units with soft time windows. In: Proceedings of the 10th Annual European Symposium on Algorithms, number 2461, pages 637-648. Springer.
• Daniela Kühn and Deryk Osthus: Topological minors in graphs of large girth, Journal of Combinatorial Theory (B), 86: 364-380.
• Daniela Kühn, Deryk Osthus, and Anusch Taraz: Large planar subgraphs in dense graphs. preprint.
• Annegret Wagler: Antiwebs are Rank-Perfect. technical report, ZIB-Report 02-07.
• Annegret Wagler: Rank-Perfect and Weakly Rank-Perfect Graphs, Methods of Operations Research, 95: 127-149.

2001

• M. Blom, Sven O. Krumke, W. E. de Paepe, and L. Stougie: The Online-TSP Against Fair Adversaries, Information and Computing, 13: 138-148. A preliminary version appeared in the Proceedings of the 4th Italian Conference on Algorithms and Complexity, 2000, vol. 1767 of Lecture Notes in Computer Science.
• Ralf Borndörfer and Robert Weismantel: Relations Among Some Combinatorial Programs, Discrete Applied Mathematics, 112: 11-26.
• D. I. Dais, C. Haase, and Günter M. Ziegler: All toric local complete intersection singularities admit projective crepant resolutions, Tohoku Math. J., 53: 95-107.
• D. I. Dais, M. Henk, and Günter M. Ziegler: Constructive methods of crepant resolutions of three-dimensional canonical toric singularities. Algorithms and applications. In preparation.
• Cristina Gomes Fernandes and Till Nierhoff: The UPS Problem. In: Alfonso Ferreira and Horst Reichel (editor): Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, volume 2010 of series LNCS, pages 238-246. Springer.
• S. Fuhrmann, Sven O. Krumke, and H.-C. Wirth: Multiple hotlink assignment. In: Proceedings of the 27th International Work-shop on Graph-Theoretic Concepts in Computer Science, number 2204, pages 189-200. Springer.
• Martin Grötschel, Sven O. Krumke, and Jörg Rambau (editor): Online Optimization of Large Scale Systems. Springer-Verlag, Berlin, Heidelberg, New York.
• D. Hauptmeier, Sven O. Krumke, and Jörg Rambau: The Online Dial-a-Ride Problem under Reasonable Load, Theoretical Computer Science.
• D. Hauptmeier, Sven O. Krumke, Jörg Rambau, and H.-C. Wirth: Euler is standing in line. In: Discrete Applied Mathematics, number 113, pages 87-107. A preliminary version appeared in the Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science, 2000, vol. 1665 of Lecture Notes in Computer Science.
• Sven O. Krumke, Madhav V. Marathe, and S. S. Ravi: Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, 7(6): 575-584. A preliminary version appeared in the Proceedings of the Second International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Dallas, Texas, 1998.
• Sven O. Krumke, W. E. de Paepe, D. Poensgen, and L. Stougie: News from the Online Traveling Repairman. In: (editor): Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, number 2136, pages 487-499. Springer.
• Sven O. Krumke, W. E. de Paepe, Jörg Rambau, and L. Stougie: Online Bincoloring. In: (editor): Proceedings of the 9th Annual European Symposium on Algorithms, number 2161, pages 74-84. Springer.
• Deryk Osthus and Anusch Taraz: Random maximal H-free graphs, Random Structures and Algorithms, 18: 61-82.
• Hans Jürgen Prömel and Anusch Taraz: Random graphs, random triangle-free graphs, and random partial orders. In: Helmut Alt (editor): Computational Discrete Mathematics, number 2122, page 98 ff. Springer.
• Annegret Wagler: Which Graphs are 'Almost' Perfect?. to appear in: The Sharpest Cut, Festschrift on the occasion of a workshop in honor of Manfred Padberg's 60th birthday, MPS/SIAM, 2001.

2000

• N. Ascheuer, Sven O. Krumke, and Jörg Rambau: Online Dial-a-Ride Problems: Minimizing the Completion Time. In: Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science, number 1170, pages 639-650.
• T. Fleiner, Volker Kaibel, and Günter Rote: Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes, European Journal on Combinatorics, 21: 121-131.
• E. Gawrilow and Michael Joswig: polymake: a Framework for Analyzing Convex Polytopes. In: G. Kalai and Günter M. Ziegler (editor): Polytopes - Combinatorics and Computation, DMV-Seminars, pages 43-74. Birkhäuser-Verlag Basel.
• Volker Kaibel and M. Wolff: Simple 0/1-Polytopes, European Journal on Combinatorics, 21: 139-144.
• Annegret Wagler: Critical Edges in Perfect Graphs. Doktorarbeit, TU Berlin.
• Günter M. Ziegler: A census of flag-vectors of 4-polytopes. In: G. Kalai and Günter M. Ziegler (editor): Polytopes - Combinatorics and Computation, DMV-Seminars, pages 105-110. Birkhäuser-Verlag Basel.
• Günter M. Ziegler: Lectures on 0/1-polytopes. In: G. Kalai and Günter M. Ziegler (editor): Polytopes - Combinatorics and Computation, DMV-Seminars, pages 1-41. Birkhäuser-Verlag Basel.

---

last modified 06/03/08 (alkox-www)