Algorithmen und Komplexität

Aktuelle Veröffentlichungen

Bücher

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

Preprints

Manuel Bodirsky und Hubie Chen: Oligomorphic Clones. 2009+. To appear in Algebra Universalis.
Manuel Bodirsky, Eric Fusy, Mihyun Kang und Stefan Vigerske: Enumeration of Unlabeled Outerplanar Graphs. 2009+. Submitted.
Hiêp Hàn und Mathias Schacht: Dirac-type results for loose Hamilton cycles in uniform hypergraphs. 2009+. submitted.
Jan Hladký und Mathias Schacht: Note on bipartite graph tilings. 2009+. submitted.
Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht und Oleg Verbitsky: Obfuscated Drawings of Planar Graphs. 2009+. submitted.
Yoshiharu Kohayakawa, Brendan Nagle, Vojtěch Rödl und Mathias Schacht: Weak regularity and linear hypergraphs. 2009+. submitted.
Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht und Endre Szemerédi: Sparse partition universal graphs for graphs of bounded degree. 2009+. submitted.
Hanno Lefmann, Yury Person, Vojtěch Rödl und Mathias Schacht: On colorings of hypergraphs without monochromatic Fano planes. 2009+. submitted.
Henry Liu und Yury Person: Highly connected coloured subgraphs via the Regularity Lemma. 2009+. submitted.
Michael Behrisch, Amin Coja-Oghlan und Mihyun Kang: The order of the giant component of random hypergraphs. January 2007. Preprint.
Michael Behrisch, Amin Coja-Oghlan und Mihyun Kang: Local limit theorems and the number of connected hypergraphs. January 2007. Preprint.
Amin Coja-Oghlan, Michael Krivelevich und Dan Vilenchik: Why almost all k-colorable graphs are easy. 2007. To appear in the Proceedings of STACS 2007.
Amin Coja-Oghlan, Konstantinos Panagiotou und Angelika Steger: On the chromatic number of random graphs. January 2007. Preprint.

Artikel

Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtěch Rödl und 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 und 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 und Mihyun Kang: A direct decomposition of 3-connected planar graphs, Séminaire Lotharingien de Combinatoire, 2009+. Accepted for publication.
Manuel Bodirsky, Clemens Gröpl und Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random, Theoretical Computer Science, 2009+. To appear.
Manuel Bodirsky und Jan Kára: The Complexity of Equality Constraint Languages, Theory of Computing Systems, 2009+. Accepted for publication.
Manuel Bodirsky und 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 und 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 und Vishal Sanwalani: Counting connected graphs and hypergraphs via the probabilistic method, Random Structures and Algorithms, 2009+. to appear.
Hiêp Hàn, Yury Person und Mathias Schacht: On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM Journal on Discrete Mathematics, 2009+. submitted.
Mihyun Kang und 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 und Mathias Schacht: Generalizations of the removal lemma, Combinatorica, 2009+. to appear; Extended abstract appeared in Proceedings of STOC 2007.
Julia Böttcher, Mathias Schacht und 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 und Mathias Schacht: Hypergraph regularity and quasi-randomness. In: Claire Mathieu (Herausgeber): Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), Seiten 227-235, 2009. ACM Press.
Yury Person und Mathias Schacht: Almost all hypergraphs without Fano planes are bipartite. In: Claire Mathieu (Herausgeber): Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), Seiten 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 und Robert Preissner: Superimposé: a 3D structural superposition server, Nucleic Acids Research, 36(Web Server Issue): 47-54, 2008.
Michael Behrisch, Amin Coja-Oghlan und Peter Liske: Die Eulertour. In: Berthold Vöcking, M. Dietzfelbinger, Helmut Alt, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer und Dorothea Wagner (Herausgeber): Taschenbuch der Algorithmen, eXamen.press, Kapitel 29, Seiten 295-301. Springer, 2008.
Julia Böttcher, Mathias Schacht und 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 und Mariano Zelke: Polyhedral tori with minimal integer coordinates, Electronic Geometry Models, 2008.10.001, 2008.
Brendan Nagle, Sayaka Olsen, Vojtěch Rödl und Mathias Schacht: On the Ramsey number of sparse 3-graphs, Graphs and Combinatorics, 24(3): 205-228, 2008.
Brendan Nagle, Vojtěch Rödl und 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 und 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 und 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, Band 4596 der Reihe Lecture Notes in Computer Science, Seiten 789-800, 2007. Springer. full version.
Christian Avart, Vojtěch Rödl und 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 und Hubie Chen: Quantified Equality Constraints. In: Logic in Computer Science (LICS07), 2007.
Manuel Bodirsky und 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 und 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 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, 2007.
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, 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 und Colin McDiarmid: Random cubic planar graphs, Random Structures and Algorithms, 30: 78-94, 2007.
Manuel Bodirsky und 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 und 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 und Anusch Taraz: Embedding spanning subgraphs of small bandwidth. In: Proceedings of EuroComb 07, Band 29 der Reihe Electron. Notes Discrete Math., Seiten 485-489, 2007. full article.
Julia Böttcher, Mathias Schacht und Anusch Taraz: On the bandwidth conjecture for 3-colourable graphs. In: Hal Gabow (Herausgeber): Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 07), Seiten 618-626, 2007. ACM Press. full article.
Amin Coja-Oghlan, Andreas Goerdt und Andre Lanka: Strong refutation heuristics for random k-SAT, Combinatorics, Probability and Computing, 16: 5-28, 2007.
Stefan Hougardy, Frank H. Lutz und Mariano Zelke: Polyhedra of genus 3 with 10 vertices and minimal coordinates, Electronic Geometry Models, 2006.02.001, 2007.
Stefan Hougardy, Frank H. Lutz und 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 und 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 und 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 und Mathias Schacht: Regular partitions of hypergraphs: Counting Lemmas, Combinatorics, Probability and Computing, 16(6): 887-901, 2007.
Vojtěch Rödl und Mathias Schacht: Regular partitions of hypergraphs: Regularity Lemmas, Combinatorics, Probability and Computing, 16(6): 833-885, 2007.
Vojtěch Rödl und Mathias Schacht: Property testing in hypergraphs and the removal lemma. In: David S. Johnson und Uriel Feige (Herausgeber): Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, June 11-13, 2007, Seiten 488-495, 2007. ACM Press. full article.
Vojtěch Rödl, Mathias Schacht, Mark Siggers und 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.

Dissertationen und Habilitationsschriften

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. Doktorarbeit, 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. Doktorarbeit, Humboldt-Universität zu Berlin, 2007.
Martin Thimm: Algorithmen im Wirkstoffdesign. Doktorarbeit, Humboldt-Universität zu Berlin, 2006.

Diplom- und Studienarbeiten

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 . Diplomarbeit, Humboldt-Universität zu Berlin, Juni 2007.
Hiep Han: Bipartite Graphen mit kleiner Bandbreite in dichten Graphen. Diplomarbeit, 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.

zuletzt geändert am 26.08.2005 (alkox-www)