Algorithmen und Komplexität

Aktuelle Veröffentlichungen

Bücher

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 und 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 und Hubie Chen: Oligomorphic Clones. 2008+. To appear in Algebra Universalis.
Manuel Bodirsky, Eric Fusy, Mihyun Kang und Stefan Vigerske: Enumeration of Unlabeled Outerplanar Graphs. 2008+. Submitted.
Hiêp Hàn, Yury Person und Mathias Schacht: On perfect matchings in uniform hypergraphs with large minimum vertex degree. 2008+. submitted.
Hiêp Hàn und Mathias Schacht: Dirac-type results for loose Hamilton cycles in uniform hypergraphs. 2008+. submitted.
Jan Hladký und Mathias Schacht: Note on bipartite graph tilings. 2008+. submitted.
Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht und Oleg Verbitsky: Obfuscated Drawings of Planar Graphs. 2008+. submitted.
Yoshiharu Kohayakawa, Brendan Nagle, Vojtěch Rödl und Mathias Schacht: Weak regularity and linear hypergraphs. 2008+. submitted.
Hanno Lefmann, Yury Person, Vojtěch Rödl und Mathias Schacht: On colorings of hypergraphs without monochromatic Fano planes. 2008+. submitted.
Henry Liu und Yury Person: Highly connected coloured subgraphs via the Regularity Lemma. 2008+. 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.
Amin Coja-Oghlan: Graph partitioning via adaptive spectral techniques. July 2006. Preprint.
Stefan Hougardy, Frank H. Lutz und Mariano Zelke: Surface Realization with the Intersection Edge Functional. July 2006. submitted.
Mariano Zelke: k-Connectivity in the Semi-Streaming Model. 2006.

Artikel

Manuel Bodirsky, Omer Gimenez, Mihyun Kang und 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 und Mihyun Kang: A direct decomposition of 3-connected planar graphs, Séminaire Lotharingien de Combinatoire, 2008+. Accepted for publication.
Manuel Bodirsky, Clemens Gröpl und Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random, Theoretical Computer Science, 2008+. To appear.
Manuel Bodirsky und Jan Kára: The Complexity of Equality Constraint Languages, Theory of Computing Systems, 2008+. Accepted for publication.
Manuel Bodirsky und 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 und Oleg Verbitsky: The first order definability of trees and sparse random graphs, Combinatorics, Probability and Computing, 2008+. to appear.
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 und Vishal Sanwalani: Counting connected graphs and hypergraphs via the probabilistic method, Random Structures and Algorithms, 2008+. to appear.
Mihyun Kang und Taral Guldahl Seierstad: The phase transition of the minimum degree random multi-graph process, Random Structures and Algorithms, 2008+. accepted for publication.
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: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), 2009. to appear.
Yury Person und Mathias Schacht: Almost all hypergraphs without Fano planes are bipartite. In: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), 2009. to appear.
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: 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.
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, Wrocław, Poland, July 9-13, Band 4596 der Reihe Lecture Notes in Computer Science, Seiten 789-800, 2007. Springer.
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.
Jørgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Šámal, Bjarne Toft und Uli Wagner: On six problems posed by Jarik Nešetřil. In: M. Klazar, J. Kratochvil, Martin Loebl, J. Matoušek, Robin Thomas und Pavel Valtr (Herausgeber): Topics in Discrete Mathematics, Band 26 der Reihe Algorithms Combin., Seiten 613-627. Springer, Berlin, 2006.
Michael Behrisch und Amin Coja-Oghlan: Zufällige Graphen. In: Wolfgang Reisig und Johann Christoph Freytag (Herausgeber): Informatik - Aktuelle Themen im historischen Kontext, Seiten 49-77, 2006. Springer.
Michael Behrisch und Anusch Taraz: Efficiently covering complex networks with cliques of similar vertices, Theoretical Computer Science, 355(1): 37-47, April 2006.
Manuel Bodirsky und Hubie Chen: Collapsibility in Infinite-Domain Quantified Constraint Satisfaction. In: Computer Science Logic (CSL06), LNCS 4207, Seiten 197-211, Szeged, Hungary, 2006.
Manuel Bodirsky und 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, Seiten 646-659, 2006. Springer Verlag.
Manuel Bodirsky und 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 und Mihyun Kang: Generating outerplanar graphs uniformly at random, Combinatorics, Probability and Computing, 15(03): 333-343, 2006.
Manuel Bodirsky und Jan Kára: The Complexity of Equality Constraint Languages. In: Proceedings of the International Computer Science Symposium in Russia (CSR06), LNCS 3967, Seiten 114-126, 2006. Springer Verlag.
Manuel Bodirsky und 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, Nummer 4051 in LNCS, Seiten 691-702, 2006. 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, 2006.
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, 2006.
Amin Coja-Oghlan und Lars Kuhtz: An improved algorithm for approximating the chromatic number of G(n,p), Information Processing Letters, 99: 234-238, 2006.
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, 2006. 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, 2006.
Ivo Grosse, Andre Gohr, Jens Keilwagen, Valentin Ziegler und 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 und Stefan Kirchner: Lower Bounds for the Relative Greedy Algorithm for Approximating Steiner Trees, Networks, 47(2): 111-115, 2006.
Stefan Hougardy und Doratha E. Vinkemeier: Approximating weighted matchings in parallel, Information Processing Letters, 99(3): 119-123, 2006.
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, 2006.
Brendan Nagle, Vojtěch Rödl und 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 und Mathias Schacht: Extremal hypergraph problems and the regularity method. In: M. Klazar, J. Kratochvil, Martin Loebl, J. Matoušek, Robin Thomas und Pavel Valtr (Herausgeber): Topics in Discrete Mathematics, Band 26 der Reihe Algorithms Combin., Seiten 247-278. Springer, Berlin, 2006.
Vojtěch Rödl, Mathias Schacht, Eduardo Tengan und Norihide Tokushige: Density theorems and extremal hypergraph problems, Israel Journal of Mathematics, 152: 371-380, 2006.

Dissertationen und Habilitationsschriften

Michael Behrisch: Stochastical models for networks in the life sciences. Doktorarbeit, Humboldt-Universität zu Berlin, 2007.
Taral Guldahl Seierstad: The phase transition in random graphs and random graph processes. Doktorarbeit, 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. Doktorarbeit, Humboldt-Universität zu Berlin, 2005.

Diplom- und Studienarbeiten

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. Diplomarbeit, 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. Diplomarbeit, Humboldt-Universität zu Berlin, 2005.
Michael Ueckerdt: Färben von zufälligen Schnittgraphen. Diplomarbeit, Humboldt-Universität zu Berlin, Juli 2005.
Mariano Zelke: Ein Approximationsalgorithmus zur Berechnung eines 2-Spanners in planaren Triangulationen. Diplomarbeit, Humboldt-Universität zu Berlin, 11/2005 2005.

zuletzt geändert am 26.08.2005 (alkox-www)