Algorithms and Complexity

Latest Publications

Books

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

Preprints

• Manuel Bodirsky and Hubie Chen: Oligomorphic Clones. 2009+. To appear in Algebra Universalis.
• Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan Vigerske: Enumeration of Unlabeled Outerplanar Graphs. 2009+. Submitted.
• Hiêp Hàn and Mathias Schacht: Dirac-type results for loose Hamilton cycles in uniform hypergraphs. 2009+. submitted.
• Jan Hladký and Mathias Schacht: Note on bipartite graph tilings. 2009+. submitted.
• Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, and Oleg Verbitsky: Obfuscated Drawings of Planar Graphs. 2009+. submitted.
• Yoshiharu Kohayakawa, Brendan Nagle, Vojtěch Rödl, and Mathias Schacht: Weak regularity and linear hypergraphs. 2009+. submitted.
• Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht, and Endre Szemerédi: Sparse partition universal graphs for graphs of bounded degree. 2009+. submitted.
• Hanno Lefmann, Yury Person, Vojtěch Rödl, and Mathias Schacht: On colorings of hypergraphs without monochromatic Fano planes. 2009+. submitted.
• Henry Liu and Yury Person: Highly connected coloured subgraphs via the Regularity Lemma. 2009+. 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.

Articles

• 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, SIAM Journal on Computing, 2009+. to appear; Extended Abstract appeared in Proceedings of ICALP 2007.
• Manuel Bodirsky, Omer Gimenez, Mihyun Kang, and Marc Noy: Enumeration and limit laws of series-parallel graphs, European Journal on Combinatorics, 2009+. 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, 2009+. Accepted for publication.
• Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random, Theoretical Computer Science, 2009+. To appear.
• Manuel Bodirsky and Jan Kára: The Complexity of Equality Constraint Languages, Theory of Computing Systems, 2009+. Accepted for publication.
• Manuel Bodirsky and Jan Kara: A Fast Algorithm and Lower Bound for Temporal Reasoning. In: Submitted, 2009+.
• 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, 2009+. to appear.
• Amin Coja-Oghlan: Solving NP-hard semirandom graph problems in polynomial expected time, Journal of Algorithms, 2009+. to appear.
• Amin Coja-Oghlan: Coloring semirandom graphs, Combinatorics, Probability and Computing, 2009+. to appear.
• Amin Coja-Oghlan, Cristopher Moore, and Vishal Sanwalani: Counting connected graphs and hypergraphs via the probabilistic method, Random Structures and Algorithms, 2009+. to appear.
• Hiêp Hàn, Yury Person, and Mathias Schacht: On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM Journal on Discrete Mathematics, 2009+. submitted.
• Mihyun Kang and Taral Guldahl Seierstad: The phase transition of the minimum degree random multi-graph process, Random Structures and Algorithms, 2009+. accepted for publication.
• Vojtěch Rödl and Mathias Schacht: Generalizations of the removal lemma, Combinatorica, 2009+. to appear; Extended abstract appeared in Proceedings of STOC 2007.
• Julia Böttcher, Mathias Schacht, and Anusch Taraz: Proof of the bandwidth conjecture of Bollobás and Komlós, Math. Ann., 343(1): 175-205, 2009. Extended abstract appeared in Electron. Notes Discrete Math. 29, pages 485-489..
• Brendan Nagle, Annika Poerschke, Vojtěch Rödl, and Mathias Schacht: Hypergraph regularity and quasi-randomness. In: Claire Mathieu (editor): Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), pages 227-235, 2009. ACM Press.
• Yury Person and Mathias Schacht: Almost all hypergraphs without Fano planes are bipartite. In: Claire Mathieu (editor): Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), pages 217-226, 2009. ACM Press.
• Valentin Ziegler: Approximating optimum branchings in linear time, Information Processing Letters, 109: 175-178, 2009.
• Raphael A. Bauer, Philip E. Bourne, Arno Formella, Cornelius Frömmel, Chritoph Gille, Andrean Goede, Aysam Guerler, Andreas Hoppe, Ernst-Walter Knapp, Thorsten Pöschel, Burghardt Wittig, Valentin Ziegler, and Robert Preissner: Superimposé: a 3D structural superposition server, Nucleic Acids Research, 36(Web Server Issue): 47-54, 2008.
• Michael Behrisch, Amin Coja-Oghlan, and Peter Liske: Die Eulertour. In: Berthold Vöcking, M. Dietzfelbinger, Helmut Alt, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer, and Dorothea Wagner (editor): Taschenbuch der Algorithmen, eXamen.press, chapter 29, pages 295-301. Springer, 2008.
• 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..
• Stefan Hougardy, Frank Lutz, and Mariano Zelke: Polyhedral tori with minimal integer coordinates, Electronic Geometry Models, 2008.10.001, 2008.
• 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.
• 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, 49(4): 633-636, 2008.
• Valentin Ziegler: Approximation algorithms for restricted Bayesian network structures, Information Processing Letters, 108: 60-63, 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, Wroclaw, Poland, July 9-13, volume 4596 of series Lecture Notes in Computer Science, pages 789-800, 2007. Springer. full version.
• 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.

Dissertations and Habilitations

• Stefan Kirchner: Untere Schranken für Steinerbaumalgorithmen und die Konstruktion von Bicliquen in dichten Graphen. Dissertation, Humboldt-Universität zu Berlin, September 2008.
• Michael Behrisch: Stochastical models for networks in the life sciences. PhD thesis, Humboldt-Universität zu Berlin, 2007.
• Mihyun Kang: Random planar structures and random graph processes. Habilitationsschrift, Humboldt-Universität zu Berlin, Juli 2007.
• Dirk Schlatter: Constrained random graph processes. Dissertation, Humboldt-Universität zu Berlin, August 2007.
• Taral Guldahl Seierstad: The phase transition in random graphs and random graph processes. PhD thesis, Humboldt-Universität zu Berlin, 2007.
• Martin Thimm: Algorithmen im Wirkstoffdesign. PhD thesis, Humboldt-Universität zu Berlin, 2006.

Diploma and Seminar Theses

• Jens K. Müller: Rooted Phylogeny Problems. Diplomarbeit, Humboldt-Universität zu Berlin, Juni 2008.
• Enkhtur Zurgaanjin: Approximiertes Zählen von linearen Hypergraphen in großen Hypergraphen. Diplomarbeit, Humboldt-Universität zu Berlin, August 2008.
• Peter Liske: Hamiltonkreise in maximal planaren Graphen. Studienarbeit, Humboldt-Universität zu Berlin, Institut für Informatik, Januar 2007.
• Yasushi Tomii: Enumeration der wohlgeschachtelten B-Zeichnungen mit Gap-Grad höchstens eins . Master thesis, Humboldt-Universität zu Berlin, Juni 2007.
• Hiep Han: Bipartite Graphen mit kleiner Bandbreite in dichten Graphen. Master thesis, Humboldt-Universitat zu Berlin, August 2006.
• Daniel Johannsen: Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time. Diplomarbeit, Humboldt-Universität zu Berlin, April 2006.
• 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.
• Valentin Ziegler: Algorithmen für die Strukturmaximierung von azyklischen gerichteten Graphen. Diplomarbeit, HU Berlin, August 2006.

---

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