Algorithmen, Struktur, Zufall

Publikationen

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

2008+

• Manuel Bodirsky, Eric Fusy, Mihyun Kang und Stefan Vigerske: Enumeration of Unlabeled Outerplanar Graphs. Submitted.
• Manuel Bodirsky, Omer Gimenez, Mihyun Kang und Marc Noy: Enumeration and limit laws of series-parallel graphs, European Journal on Combinatorics. Accepted for publication.
• Manuel Bodirsky, Clemens Gröpl und Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random, Theoretical Computer Science. To appear.
• Hans L. Bodlaender, F. van den Eijkhof und 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 und Taral Guldahl Seierstad: The phase transition of the minimum degree random multi-graph process, Random Structures and Algorithms. accepted for publication.
• Mihyun Kang und 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 und 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), Seiten 356-365.
• Manuel Bodirsky, Clemens Gröpl, Daniel Johannsen und 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 und Colin McDiarmid: Random cubic planar graphs, Random Structures and Algorithms, 30: 78-94.
• Amin Coja-Oghlan, Andreas Goerdt und Andre Lanka: Strong refutation heuristics for random k-SAT, Combinatorics, Probability and Computing, 16: 5-28.

2006

• Manuel Bodirsky und Mihyun Kang: Generating outerplanar graphs uniformly at random, Combinatorics, Probability and Computing, 15(03): 333-343.
• Manuel Bodirsky, Mihyun Kang und Oleg Verbitsky: On the logical complexity of convex polygon dissections. Archiv der Mathematik.
• H. L. Bodlaender und A. M. C. A. Koster: Safe Separators for Treewidth, Discrete Mathematics, 306(3): 337-350.
• H. L. Bodlaender, T. Wolle und A. M. C. A. Koster: Contraction and Treewidth Lower Bounds, Journal of Graph Algorithms and Applications, 10(1): 5-49.
• Peter Cameron, Mihyun Kang und 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, Nummer 4051 in LNCS, Seiten 691-702. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan, Andreas Goerdt und Andre Lanka: Spectral partitioning of random graphs with given expected degrees. In: Gonzalo Navarro, Leopoldo Bertossi und Yoshiharu Kohayakawa (Herausgeber): 4th IFIP International Conference on Theoretical Computer Science - TCS 2006 (19th World Computer Congress 2006, Santiago de Chile), Seiten 271-282.
• Amin Coja-Oghlan, Sven O. Krumke und 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 und Lars Kuhtz: An improved algorithm for approximating the chromatic number of G(n,p), Information Processing Letters, 99: 234-238.
• Amin Coja-Oghlan und Andre Lanka: The spectral gap of random graphs with given expected degrees. In: ICALP, Nummer 4051 in LNCS, Seiten 15-26. Springer.
• Amin Coja-Oghlan, Cristopher Moore und 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 und 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 und A. Zymolka: Availability and Cost Based Evaluation of Demand-wise Shared Protection. In: Proceedings 7th ITG-Workshop on Photonic Networks, Seiten 161-168, Leipzig, Germany. VDE Verlag GmbH.
• Mihyun Kang, Youngmee Koh, Tomasz Łuczak und Sangwook Ree: The connectivity threshold for the min-degree random graph process, Random Structures and Algorithms, 29: 105-120.
• Mihyun Kang und 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 und 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, Seiten 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), Band LNCS 3404, Seiten 110-120, Stuttgart. Springer.
• Manuel Bodirsky, Omer Gimenez, Mihyun Kang und 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, Seiten 383 - 388.
• Manuel Bodirsky, Clemens Gröpl und Mihyun Kang: Sampling unlabeled biconnected planar graphs. In: Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC05), LNCS 3827, Seiten 593-603. Springer Verlag.
• Hans L. Bodlaender, F. van den Eijkhof und Arie M. C. A. Koster: Pre-processing rules for triangulation of probabilistic networks, Computational Intelligence, 21(3): 286-305.
• Hans L. Bodlaender, A. Grigoriev und Arie M. C. A. Koster: Treewidth Lower Bounds with Brambles. In: G. S. Brodal und S. Leonardi (Herausgeber): Proceedings 13th Annual European Symposium on Algorithms, ESA2005, Band 3669 der Reihe Lecture Notes in Computer Science, Seiten 391-402. Springer.
• Hans L. Bodlaender, Arie M. C. A. Koster und T. Wolle: Degree-Based Treewidth Lower Bounds. In: Proceedings of 4th International Workshop on Efficient and Experimental Algorithms, WEA 2005, Band 3503 der Reihe Lecture Notes in Computer Science, Seiten 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 und 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 und 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 und Adrian Zymolka: Demand-wise Shared Protection revisited: A new model for survivable network design. In: Proceedings of INOC 2005, Seiten 100-105, Lisbon, Portugal. International Network Optimization Conference.
• C. Gruber, Arie M. C. A. Koster, S. Orlowski, R. Wessäly und Adrian Zymolka: A Computational Study for Demand-wise Shared Protection. In: Proceedings of DRCN 2005, Seiten 421-428, Naples, Italy. Design of Reliable Communication Networks.
• I. V. Hicks und E. Kolotoğlu: Branch and Tree Decomposition Techniques for Discrete Optimization. In: J. Cole Smith (Herausgeber): TutORials 2005, TutORials in Operations Research Series, Kapitel 1, Seiten 1-29. INFORMS Annual Meeting, New Orleans.
• Benjamin Hiller: Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load. Technischer Bericht 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 und 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 und Günter M. Ziegler: The simplex algorithm in dimension three, SIAM Journal on Computing, 34: 475-497.
• Mihyun Kang und Oleg Pikhurko: Maximum K_r+1-free graphs which are not r-partite, Mat. Studii, 24: 12-20.
• A. M. C. A. Koster und A. K. Wagler: Comparing Imperfection Ratio and Imperfection Index for Graph Classes. ZIB-Report 05-50, ZIB.
• Arie M. C. A. Koster und Adrian Zymolka: Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks. In: Proceedings of INOC 2005, Seiten 44-51, Lisbon, Portugal. International Network Optimization Conference.
• Arie M. C. A. Koster und Adrian Zymolka: On cycles and the stable multi-set polytope, Discrete Optimization, 2(3): 241-255.
• Arie M. C. A. Koster und Adrian Zymolka: Provably Good Solutions for Wavelength Assignment in Optical Networks. In: Proceedings of ONDM 2005, Seiten 335-345, Milan, Italy. The 9th IFIP Working Conference on Optical Network Design & Modelling.
• Daniela Kühn und Deryk Osthus: Spanning triangulations in graphs, Journal of Graph Theory, 49: 205-233.
• Daniela Kühn und Deryk Osthus: Packings in dense regular graphs, Combinatorics, Probability and Computing, 14: 325-337.
• Daniela Kühn und Deryk Osthus: 4-cycles in graphs without a forbidden even cycle, Journal of Graph Theory, 48: 147-156.
• Carsten Lange und Günter M. Ziegler: On generalized Kneser hypergraph colorings. April. preprint, 8 pages.
• Torsten Schöneborn und Günter M. Ziegler: The Topological Tverberg Problem and winding number, Journal Combinatorial Theory, 112: 82-104.

2004

• Manuel Bodirsky, Clemens Gröpl und Mihyun Kang: Decomposing, counting, and generating unlabeled cubic planar graphs uniformly at random. Submitted.
• Hans L. Bodlaender und 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 und T. Wolle: Contraction and Treewidth Lower Bounds. In: Proceedings of 12th Annual European Symposium on Algorithms (ESA 2004), Band 3221 der Reihe Lecture Notes in Computer Science, Seiten 628-639.
• Hans L. Bodlaender, Arie M. C. A. Koster und T. Wolle: Degree-Based Treewidth Lower Bounds. ZIB-Report 04-44, Zuse Institute Berlin, Berlin.
• Hans L. Bodlaender, Arie M. C. A. Koster und T. Wolle: A note on Contraction Degeneracy. ZIB-Report 04-43, Zuse Institute Berlin, Berlin.
• Pierce G. Buckley und 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ö und Donald Sannella (Herausgeber): Automata, Languages and Programming: 31st International Colloquium (ICALP 2004), Band 3142 der Reihe LNCS, Seiten 383-395. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan, Andreas Goerdt, Andre Lanka und Frank Schädlich: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT, Theoretical Computer Science, 329: 1-45.
• Amin Coja-Oghlan und 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 und 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 und 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 und Georg L. Nemhauser (Herausgeber): Integer Programming and Combinatorial Optimization (IPCO X), Nummer 3064, Seiten 401-415. Springer.
• Volker Kaibel: On the Expansion of Graphs of 0/1-Polytopes. In: Martin Grötschel (Herausgeber): The Sharpest Cut: The Impact of Manfred Padberg and His Work, MPS-SIAM Series on Optimization 4, Seiten 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 und T. Vredeveld: How to whack moles. In: (Herausgeber): In Proceedings of the 1st Workshop on on Approximation and Online Algorithms, Band 2909, Seiten 192-205. Springer.
• Daniela Kühn und Deryk Osthus: Complete minors in $K_s,s$-free graphs, Combinatorica, 25: 49-61.
• Daniela Kühn und 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 und Deryk Osthus: Large topological cliques in graphs without a 4-cycle, Combinatorics, Probability and Computing, 13: 93-102.
• Daniela Kühn und 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 und Deryk Osthus: Induced subdivisions in $K_s,s$-free graphs of large average degree, Combinatorica, 24: 287-304.
• Jiří Matoušek und Günter M. Ziegler: Topological lower bounds for the chromatic number: A hierarchy, Jahresbericht der Deutschen Mathematiker-Vereinigung, 106: 71-90.
• Julian Pfeifle und Günter M. Ziegler: On the Monotone Upper Bound Problem, Experimental Mathematics, 13: 1-11.
• Florian Pfender und 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. Technischer Bericht, ZIB-Report 04-06.
• Annegret Wagler: Relaxing Perfectness: Which Graphs are Almost Perfect?, Seiten 77-96.

2003

• L. Becchetti, S. Leonardi, Alberto Marchetti-Spaccamela, G. Schäfer und 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), Seiten 462-471.
• Manuel Bodirsky, Clemens Gröpl und 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, Seiten 1095-1107. Springer Verlag. Journal version to appear in Theoretical Computer Science.
• Manuel Bodirsky, Clemens Gröpl und 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, Seiten 61-66. Journal version submitted.
• C. Burch, Robert Carr, Sven O. Krumke, Madhav V. Marathe, C. Phillips und E. Sundberg: A decomposition-based pseudoapproximation algorithm for network inhibition, Seiten 51-68. Kluwer Academic Press.
• Amin Coja-Oghlan, Sven O. Krumke und 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, Band 2906 der Reihe LNCS, Seiten 605-614. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan, Sven O. Krumke und 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, Seiten 48-50. Available as ZIB-Report 03-12.
• Amin Coja-Oghlan, Sven O. Krumke und Till Nierhoff: Average case analysis of a hard dial-a-ride-problem. Technischer Bericht, ZIB-Report 03-12, Konrad-Zuse-Zentrum für Informationstechnik 200.
• Amin Coja-Oghlan, Cristopher Moore und Vishal Sanwalani: MAX k-CUT and approximating the chromatic number of random graphs. In: J. C. M. Baeten, Jan Karel Lenstra, J. Parrow und Gerhard J. Woeginger (Herausgeber): Automata, Languages and Programming (30th International Colloquium, ICALP 2003), Band 2719 der Reihe LNCS, Seiten 200-211. Springer. JOURNAL VERSION.
• Amin Coja-Oghlan und Anusch Taraz: Colouring random graphs in polynomial expected time. In: Helmut Alt und M. Habib (Herausgeber): STACS 2003, Band 2607 der Reihe LNCS, Seiten 487-498. Springer. JOURNAL VERSION.
• Volker Kaibel und A. Remshagen: On the graph-density of random 0/1-polytopes. In: Sanjeev Arora, Klaus Jansen, Jose D. P. Rolim und A. Sahai (Herausgeber): Approximation, Randomization, and Combinatorial Optimization (Proc. RANDOM03), Nummer 2764, Seiten 318-328. Springer.
• Volker Kaibel und Günter M. Ziegler: Counting Lattice Triangulations. In: C. D. Wensley (Herausgeber): Surveys in Combinatorics 2003, Nummer http://arxiv.org/abs/math/0211268, Seiten 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 und 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 und Adrian Zymolka: Polyhedral investigations on stable multi-sets. Technischer Bericht, ZIB-Report 03-10.
• Sven O. Krumke, R. Liu, E. L. Lloyd, Madhav V. Marathe, R. Ramanathan und 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, Nummer 2865, Seiten 187-198. Springer.
• Sven O. Krumke, Madhav V. Marathe, D. Poensgen, S. S. Ravi und H.-C. Wirth: Budgeted maximum graph coverage. In: Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Nummer 2573, Seiten 321-332. Springer.
• Sven O. Krumke, W. E. de Paepe, D. Poensgen und 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 und Deryk Osthus: Minors in graphs of large girth, Random Structures and Algorithms, 22: 213-225.
• Daniela Kühn und Deryk Osthus: Partitions of graphs of high minimum degree or connectivity, Journal of Combinatorial Theory (B), 88: 29-43.
• Daniela Kühn und Deryk Osthus: Extremal connectivity for topological cliques in bipartite graphs. submitted.
• J. Marenco und Annegret Wagler: Chromatic Scheduling Polytopes coming from the Bandwidth Allocation Problem in Point-to-Multipoint Radio Access Systems. Technischer Bericht, ZIB-Report 03-39.
• A. Pêcher und Annegret Wagler: A Construction for Non-Rank Facets of Stable Set Polytopes of Webs. Technischer Bericht, ZIB-Report 03-21.
• A. Pêcher und Annegret Wagler: On non-rank Facets in Stable Set Polytopes of Webs with Clique Number Four. Technischer Bericht, 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 und 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. Technischer Bericht, 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. Technischer Bericht, 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 und W. Rytter (Herausgeber): Mathematical Foundations of Computer Science 2002, Band 2420 der Reihe LNCS, Seiten 201-211. JOURNAL VERSION.
• Amin Coja-Oghlan: Finding sparse induced subgraphs of semirandom graphs. In: Jose D. P. Rolim und S. Vadhan (Herausgeber): Randomization and approximation techniques in computer science, Band 2483 der Reihe LNCS, Seiten 139-148. Springer. JOURNAL VERSION.
• Martin Grötschel und M. Henk: On the Representation of Polyhedra by Polynomial Inequalities. Technischer Bericht, ZIB-Report 02-15. to appear in: Discrete and Computational Geometry.
• Martin Grötschel, Sven O. Krumke, Jörg Rambau und L. M. Torres: Making the yellow angels fly: Online dispatching of service vehicles in real time, Siam News, 35(1): 10-11.
• Stefan Hougardy und Annegret Wagler: Perfectness is an Elusive Graph Property. Technischer Bericht, ZIB-Report 02-11.
• Volker Kaibel, Rafael Mechtel, Micha Sharir und Günter M. Ziegler: The random edge rule for three-dimensional linear programs. Dec. Preprint, TU Berlin.
• Volker Kaibel und 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 und 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 und 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, Nummer 2462, Seiten 200-214. Springer.
• Sven O. Krumke, M. Lipmann, W. E. de Paepe, D. Poensgen, Jörg Rambau, L. Stougie und 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 und 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, Nummer 2573, Seiten 333-344. Springer.
• Sven O. Krumke und 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 und 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, Nummer 2461, Seiten 637-648. Springer.
• Daniela Kühn und Deryk Osthus: Topological minors in graphs of large girth, Journal of Combinatorial Theory (B), 86: 364-380.
• Daniela Kühn, Deryk Osthus und Anusch Taraz: Large planar subgraphs in dense graphs. preprint.
• Annegret Wagler: Antiwebs are Rank-Perfect. Technischer Bericht, 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 und 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 und Robert Weismantel: Relations Among Some Combinatorial Programs, Discrete Applied Mathematics, 112: 11-26.
• D. I. Dais, C. Haase und 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 und Günter M. Ziegler: Constructive methods of crepant resolutions of three-dimensional canonical toric singularities. Algorithms and applications. In preparation.
• Cristina Gomes Fernandes und Till Nierhoff: The UPS Problem. In: Alfonso Ferreira und Horst Reichel (Herausgeber): Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, Band 2010 der Reihe LNCS, Seiten 238-246. Springer.
• S. Fuhrmann, Sven O. Krumke und H.-C. Wirth: Multiple hotlink assignment. In: Proceedings of the 27th International Work-shop on Graph-Theoretic Concepts in Computer Science, Nummer 2204, Seiten 189-200. Springer.
• Martin Grötschel, Sven O. Krumke und Jörg Rambau (Herausgeber): Online Optimization of Large Scale Systems. Springer-Verlag, Berlin, Heidelberg, New York.
• D. Hauptmeier, Sven O. Krumke und Jörg Rambau: The Online Dial-a-Ride Problem under Reasonable Load, Theoretical Computer Science.
• D. Hauptmeier, Sven O. Krumke, Jörg Rambau und H.-C. Wirth: Euler is standing in line. In: Discrete Applied Mathematics, Nummer 113, Seiten 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 und 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 und L. Stougie: News from the Online Traveling Repairman. In: (Herausgeber): Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, Nummer 2136, Seiten 487-499. Springer.
• Sven O. Krumke, W. E. de Paepe, Jörg Rambau und L. Stougie: Online Bincoloring. In: (Herausgeber): Proceedings of the 9th Annual European Symposium on Algorithms, Nummer 2161, Seiten 74-84. Springer.
• Deryk Osthus und Anusch Taraz: Random maximal H-free graphs, Random Structures and Algorithms, 18: 61-82.
• Hans Jürgen Prömel und Anusch Taraz: Random graphs, random triangle-free graphs, and random partial orders. In: Helmut Alt (Herausgeber): Computational Discrete Mathematics, Nummer 2122, Seite 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 und 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, Nummer 1170, Seiten 639-650.
• T. Fleiner, Volker Kaibel und Günter Rote: Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes, European Journal on Combinatorics, 21: 121-131.
• E. Gawrilow und Michael Joswig: polymake: a Framework for Analyzing Convex Polytopes. In: G. Kalai und Günter M. Ziegler (Herausgeber): Polytopes - Combinatorics and Computation, DMV-Seminars, Seiten 43-74. Birkhäuser-Verlag Basel.
• Volker Kaibel und 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 und Günter M. Ziegler (Herausgeber): Polytopes - Combinatorics and Computation, DMV-Seminars, Seiten 105-110. Birkhäuser-Verlag Basel.
• Günter M. Ziegler: Lectures on 0/1-polytopes. In: G. Kalai und Günter M. Ziegler (Herausgeber): Polytopes - Combinatorics and Computation, DMV-Seminars, Seiten 1-41. Birkhäuser-Verlag Basel.

---

zuletzt geändert am 03.06.2008 (alkox-www)