Algorithms and Complexity

Latest Publications

Books

• Manuel Bodirsky: Constraint Satisfaction Problems with Infinite Templates, 2008+. Survey, submitted.

Preprints

• Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtěch Rödl, and Mathias Schacht: Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions. 2008+. submitted; Extended Abstract appeared in Proceedings of ICALP 2007.
• Manuel Bodirsky and Hubie Chen: Oligomorphic Clones. 2008+. To appear in Algebra Universalis.
• Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan Vigerske: Enumeration of Unlabeled Outerplanar Graphs. 2008+. Submitted.
• Hiêp Hàn, Yury Person, and Mathias Schacht: On perfect matchings in uniform hypergraphs with large minimum vertex degree. 2008+. submitted.
• Hiêp Hàn and Mathias Schacht: Dirac-type results for loose Hamilton cycles in uniform hypergraphs. 2008+. submitted.
• Jan Hladký and Mathias Schacht: Note on bipartite graph tilings. 2008+. submitted.
• Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, and Oleg Verbitsky: Obfuscated Drawings of Planar Graphs. 2008+. submitted.
• Yoshiharu Kohayakawa, Brendan Nagle, Vojtěch Rödl, and Mathias Schacht: Weak regularity and linear hypergraphs. 2008+. submitted.
• Hanno Lefmann, Yury Person, Vojtěch Rödl, and Mathias Schacht: On colorings of hypergraphs without monochromatic Fano planes. 2008+. submitted.
• Brendan Nagle, Annika Poerschke, Vojtěch Rödl, and Mathias Schacht: On algorithmic hypergraph regularity. 2008+. submitted.
• Yury Person and Mathias Schacht: Almost all hypergraphs without Fano planes are bipartite. 2008+. submitted.
• Michael Behrisch, Amin Coja-Oghlan, and Mihyun Kang: The order of the giant component of random hypergraphs. January 2007. Preprint.
• Michael Behrisch, Amin Coja-Oghlan, and Mihyun Kang: Local limit theorems and the number of connected hypergraphs. January 2007. Preprint.
• Amin Coja-Oghlan, Michael Krivelevich, and Dan Vilenchik: Why almost all k-colorable graphs are easy. 2007. To appear in the Proceedings of STACS 2007.
• Amin Coja-Oghlan, Konstantinos Panagiotou, and Angelika Steger: On the chromatic number of random graphs. January 2007. Preprint.
• Stefan Hougardy, Frank Lutz, and Mariano Zelke: Polyhedral Tori with minimal coordinates. 2007. submitted.
• Amin Coja-Oghlan: Graph partitioning via adaptive spectral techniques. July 2006. Preprint.
• Stefan Hougardy, Frank H. Lutz, and Mariano Zelke: Surface Realization with the Intersection Edge Functional. July 2006. submitted.
• Mariano Zelke: k-Connectivity in the Semi-Streaming Model. 2006.

Articles

• Manuel Bodirsky, Omer Gimenez, Mihyun Kang, and Marc Noy: Enumeration and limit laws of series-parallel graphs, European Journal on Combinatorics, 2008+. Accepted for publication.
• Manuel Bodirsky, Clemens Gröpl, Daniel Johannsen, and Mihyun Kang: A direct decomposition of 3-connected planar graphs, Séminaire Lotharingien de Combinatoire, 2008+. Accepted for publication.
• Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random, Theoretical Computer Science, 2008+. To appear.
• Manuel Bodirsky and Jan Kára: The Complexity of Equality Constraint Languages, Theory of Computing Systems, 2008+. Accepted for publication.
• Manuel Bodirsky and Jan Kara: A Fast Algorithm and Lower Bound for Temporal Reasoning. In: Submitted, 2008+.
• T. Bohman, A. Frieze, T. Luczak, Oleg Pikhurko, C. Smyth, J. Spencer, and Oleg Verbitsky: The first order definability of trees and sparse random graphs, Combinatorics, Probability and Computing, 2008+. to appear.
• Julia Böttcher, Mathias Schacht, and Anusch Taraz: Proof of the bandwidth conjecture of Bollobás and Komlós, Math. Ann., 2008+. to appear; Extended abstract appeared in Electron. Notes Discrete Math. 29, pages 485-489..
• Amin Coja-Oghlan: Solving NP-hard semirandom graph problems in polynomial expected time, Journal of Algorithms, 2008+. to appear.
• Amin Coja-Oghlan: Coloring semirandom graphs, Combinatorics, Probability and Computing, 2008+. to appear.
• Amin Coja-Oghlan, Cristopher Moore, and Vishal Sanwalani: Counting connected graphs and hypergraphs via the probabilistic method, Random Structures and Algorithms, 2008+. to appear.
• Mihyun Kang and Taral Guldahl Seierstad: The phase transition of the minimum degree random multi-graph process, Random Structures and Algorithms, 2008+. accepted for publication.
• Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, and Endre Szemerédi: A note on perfect matchings in uniform hypergraphs with large minimum collective degree, Commentationes Mathematicae Universitatis Carolinae, 2008+. to appear.
• Vojtěch Rödl and Mathias Schacht: Generalizations of the removal lemma, Combinatorica, 2008+. to appear; Extended abstract appeared in Proceedings of STOC 2007.
• Julia Böttcher, Mathias Schacht, and Anusch Taraz: Spanning 3-colourable subgraphs of small bandwidth in dense graphs, Journal of Combinatorial Theory (B), 98(4): 752–777, 2008. Extended abstract appeared in Proceedings of SODA 2007, pages 618-626..
• Brendan Nagle, Sayaka Olsen, Vojtěch Rödl, and Mathias Schacht: On the Ramsey number of sparse 3-graphs, Graphs and Combinatorics, 24(3): 205-228, 2008.
• Brendan Nagle, Vojtěch Rödl, and Mathias Schacht: Note on the 3-graph counting lemma, Discrete Mathematics, 308(19): 4501-4517, 2008.
• Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtěch Rödl, and Mathias Schacht: Quasi-randomness and algorithmic regularity for graphs with general degree distributions. In: Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wrocław, Poland, July 9-13, volume 4596 of series Lecture Notes in Computer Science, pages 789-800, 2007. Springer.
• Christian Avart, Vojtěch Rödl, and Mathias Schacht: Every monotone 3-graph property is testable, SIAM Journal on Discrete Mathematics, 21(1): 73-92, 2007. Extended abstract appeared in: Electron. Notes Discrete Math. 22, pages 539-542.
• Michael Behrisch: Component evolution in random intersection graphs, Electronic Journal of Combinatorics, 14(1), 2007.
• Manuel Bodirsky: Cores of Countably Categorical Structures, Logical Methods in Computer Science, 2007. DOI: 10.2168/LMCS-3(1:2).
• Manuel Bodirsky and Hubie Chen: Quantified Equality Constraints. In: Logic in Computer Science (LICS07), 2007.
• Manuel Bodirsky and Hubie Chen: Qualitative Temporal and Spatial Reasoning Revisited. In: Proceedings of the 16th EACSL Annual Conference on Computer Science and Logic (CSL07), 2007.
• Manuel Bodirsky, Hubie Chen, Jan Kára, and Timo von Oertzen: Maximal Infinite-valued Constraint Languages. In: International Colloquium on Colloquium on Automata, Languages and Programming (ICALP07), 2007. To appear.
• 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, 2007.
• 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, 2007. 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, 2007.
• Manuel Bodirsky and Martin Kutz: Determining the Consistency of Partial Tree Descriptions, Artificial Intelligence, 171: 185-196, 2007.
• Béla Bollobás, Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht, and Anusch Taraz: Essentially infinite colourings of hypergraphs, Proceedings of the London Mathematical Society, 95(3): 709-–734, 2007. Extended abstract appeared in: Electron. Notes Discrete Math. 19, pages 179-185..
• Julia Böttcher, Mathias Schacht, and Anusch Taraz: Embedding spanning subgraphs of small bandwidth. In: Proceedings of EuroComb 07, volume 29 of series Electron. Notes Discrete Math., pages 485-489, 2007. full article.
• Julia Böttcher, Mathias Schacht, and Anusch Taraz: On the bandwidth conjecture for 3-colourable graphs. In: Hal Gabow (editor): Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 07), pages 618-626, 2007. ACM Press. full article.
• Amin Coja-Oghlan, Andreas Goerdt, and Andre Lanka: Strong refutation heuristics for random k-SAT, Combinatorics, Probability and Computing, 16: 5-28, 2007.
• Stefan Hougardy, Frank H. Lutz, and Mariano Zelke: Polyhedra of genus 3 with 10 vertices and minimal coordinates, Electronic Geometry Models, 2006.02.001, 2007.
• Stefan Hougardy, Frank H. Lutz, and Mariano Zelke: Polyhedra of genus 2 with 10 vertices and minimal coordinates, Electronic Geometry Models, 2005.08.001, 2007.
• Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht, Papa Sissokho, and Jozef Skokan: Turán's theorem for pseudo-random graphs, Journal of Combinatorial Theory (A), 114(4): 631-657, 2007.
• Vojtěch Rödl, Andrzej Ruciński, and Mathias Schacht: Ramsey properties of random k-partite k-uniform hypergraphs, SIAM Journal on Discrete Mathematics, 21(2): 442-460, 2007.
• Vojtěch Rödl and Mathias Schacht: Regular partitions of hypergraphs: Counting Lemmas, Combinatorics, Probability and Computing, 16(6): 887-901, 2007.
• Vojtěch Rödl and Mathias Schacht: Regular partitions of hypergraphs: Regularity Lemmas, Combinatorics, Probability and Computing, 16(6): 833-885, 2007.
• Vojtěch Rödl and Mathias Schacht: Property testing in hypergraphs and the removal lemma. In: David S. Johnson and Uriel Feige (editor): Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, June 11-13, 2007, pages 488-495, 2007. ACM Press. full article.
• Vojtěch Rödl, Mathias Schacht, Mark Siggers, and Norihide Tokushige: Integer and fractional packings of hypergraphs, Journal of Combinatorial Theory (B), 97(2): 245-268, 2007.
• Mariano Zelke: Optimal Per-Edge Processing Times in the Semi-Streaming Model, Information Processing Letters, 104(3): 106-112, 2007.
• Jørgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Šámal, Bjarne Toft, and Uli Wagner: On six problems posed by Jarik Nešetřil. In: M. Klazar, J. Kratochvil, Martin Loebl, J. Matoušek, Robin Thomas, and Pavel Valtr (editor): Topics in Discrete Mathematics, volume 26 of series Algorithms Combin., pages 613-627. Springer, Berlin, 2006.
• Michael Behrisch and Amin Coja-Oghlan: Zufällige Graphen. In: Wolfgang Reisig and Johann Christoph Freytag (editor): Informatik - Aktuelle Themen im historischen Kontext, pages 49-77, 2006. Springer.
• Michael Behrisch and Anusch Taraz: Efficiently covering complex networks with cliques of similar vertices, Theoretical Computer Science, 355(1): 37-47, April 2006.
• Manuel Bodirsky and Hubie Chen: Collapsibility in Infinite-Domain Quantified Constraint Satisfaction. In: Computer Science Logic (CSL06), LNCS 4207, pages 197-211, Szeged, Hungary, 2006.
• Manuel Bodirsky and Víctor Dalmau: Datalog and Constraint Satisfaction with Infinite Templates. In: Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS06), Marseille, LNCS 3884, pages 646-659, 2006. Springer Verlag.
• Manuel Bodirsky and Mihyun Kang: Generating outerplanar graphs uniformly at random, Combinatorics, Probability and Computing, 15: 333-343, 2006. An earlier version of the paper was presented at the 1st workshop on Algorithms for Listing, Counting, and Enumeration (ALICE03)..
• Manuel Bodirsky and Mihyun Kang: Generating outerplanar graphs uniformly at random, Combinatorics, Probability and Computing, 15(03): 333-343, 2006.
• Manuel Bodirsky and Jan Kára: The Complexity of Equality Constraint Languages. In: Proceedings of the International Computer Science Symposium in Russia (CSR06), LNCS 3967, pages 114-126, 2006. Springer Verlag.
• Manuel Bodirsky and Jaroslav Nešetřil: Constraint Satisfaction with Countable Homogeneous Templates, Journal of Logic and Computation (JLC), 16(3): 359-373, 2006.
• Amin Coja-Oghlan: A spectral heuristic for bisecting random graphs, Random Structures and Algorithms, 29: 351-398, 2006.
• Amin Coja-Oghlan: Finding large independent sets in polynomial expected time, Combinatorics, Probability and Computing, 15: 731-751, 2006.
• Amin Coja-Oghlan: An adaptive spectral heuristic for partitioning random graphs. In: ICALP, number 4051 in LNCS, pages 691-702, 2006. 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, 2006.
• 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, 2006.
• Amin Coja-Oghlan and Lars Kuhtz: An improved algorithm for approximating the chromatic number of G(n,p), Information Processing Letters, 99: 234-238, 2006.
• 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, 2006. 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, 2006.
• Ivo Grosse, Andre Gohr, Jens Keilwagen, Valentin Ziegler, and Stefan Hougardy: Reconstruction of Bayesian networks from mRNA and metabolite expression data. In: Systems Biology: Global Regulation of Gene Expression, 2006.
• Stefan Hougardy: Classes of perfect graphs, Discrete Mathematics, 306(19-20): 2529-2571, 2006.
• Stefan Hougardy: On a conjecture of Hoàng and Tu concerning perfectly orderable graphs, Discrete Mathematics, 306(22): 2962-2963, 2006.
• Stefan Hougardy and Stefan Kirchner: Lower Bounds for the Relative Greedy Algorithm for Approximating Steiner Trees, Networks, 47(2): 111-115, 2006.
• Stefan Hougardy and Doratha E. Vinkemeier: Approximating weighted matchings in parallel, Information Processing Letters, 99(3): 119-123, 2006.
• 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, 2006.
• Brendan Nagle, Vojtěch Rödl, and Mathias Schacht: The counting lemma for regular k-uniform hypergraphs, Random Structures and Algorithms, 28(2): 113-179, 2006.
• Brendan Nagle, Vojtěch Rödl, and Mathias Schacht: Extremal hypergraph problems and the regularity method. In: M. Klazar, J. Kratochvil, Martin Loebl, J. Matoušek, Robin Thomas, and Pavel Valtr (editor): Topics in Discrete Mathematics, volume 26 of series Algorithms Combin., pages 247-278. Springer, Berlin, 2006.
• Vojtěch Rödl, Mathias Schacht, Eduardo Tengan, and Norihide Tokushige: Density theorems and extremal hypergraph problems, Israel Journal of Mathematics, 152: 371-380, 2006.

Dissertations and Habilitations

• Michael Behrisch: Stochastical models for networks in the life sciences. PhD thesis, Humboldt-Universität zu Berlin, 2007.
• Taral Guldahl Seierstad: The phase transition in random graphs and random graph processes. PhD thesis, Humboldt-Universität zu Berlin, 2007.
• Amin Coja-Oghlan: Spectral techniques, semidefinite programs, and random graphs. Habilitationsschrift, Humboldt Universität zu Berlin, Institut für Informatik, 2005.
• Martin Thimm: Algorithmen im Wirkstoffdesign. PhD thesis, Humboldt-Universität zu Berlin, 2005.

Diploma and Seminar Theses

• Peter Liske: Hamiltonkreise in maximal planaren Graphen. Studienarbeit, Humboldt-Universität zu Berlin, Institut für Informatik, Januar 2007.
• Matthias Killat: Verwendung von Outward Rotations zur approximativen Lösung von Max Cut . Studienarbeit, Humboldt-Universität zu Berlin, Institut für Informatik, August 2006.
• Julia Böttcher: Coloring sparse random k-colorable graphs in polynomial expected time. Master thesis, Humboldt-Universität zu Berlin, Januar 2005.
• Lukas Dölle: Untersuchung der Laufzeit des Random-Walk-Algorithmus auf zufälligen 2-CNF. Diplomarbeit, Humboldt-Universität zu Berlin, September 2005.
• Lukas Dölle: Untersuchung der Laufzeit des Random-Walk-Algorithmus. Studienarbeit, Humboldt-Universität zu Berlin, August 2005.
• Mike Löffler: Counting and Uniform Generation of Labeled Planar Structures. Master thesis, Humboldt-Universität zu Berlin, 2005.
• Michael Ueckerdt: Färben von zufälligen Schnittgraphen. Master thesis, Humboldt-Universität zu Berlin, Juli 2005.
• Mariano Zelke: Ein Approximationsalgorithmus zur Berechnung eines 2-Spanners in planaren Triangulationen. Master thesis, Humboldt-Universität zu Berlin, 11/2005 2005.

---

last modified 08/26/05 (alkox-www)