2008+

2007

2006

2005

2004

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)