DFG Forschungszentrum Matheon, Algorithmen und Komplexität

Analyse und Modellierung komplexer Netzwerke
(Projekt A5)

• 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.
• Michael Behrisch: Component evolution in random intersection graphs, Electronic Journal of Combinatorics, 14(1), 2007.
• Amin Coja-Oghlan, Andreas Goerdt und Andre Lanka: Strong refutation heuristics for random k-SAT, Combinatorics, Probability and Computing, 16: 5-28, 2007.
• Michael Behrisch und Anusch Taraz: Efficiently covering complex networks with cliques of similar vertices, Theoretical Computer Science, 355(1): 37-47, April 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, 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, Cristopher Moore und Vishal Sanwalani: MAX k-CUT and approximating the chromatic number of random graphs, Random Structures and Algorithms, 28: 289-322, 2006.
• Michael Behrisch, Anusch Taraz und Michael Ueckerdt: Colouring random intersection graphs and complex networks. 2005. submitted.
• Amin Coja-Oghlan: The Lovasz number of random graphs, Combinatorics, Probability and Computing, 14: 439-465, 2005.
• Amin Coja-Oghlan: On the Laplacian eigenvalues of G(n,p). 2005. Preprint.
• 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, 2004. 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, 2004.
• Amin Coja-Oghlan und Anusch Taraz: Exact and approximative algorithms for coloring G(n,p), Random Structures and Algorithms, 24(3): 259-278, May 2004.
• Stefan Hougardy, Nicolas Rocca und Martin Thimm: COSMOS. November 2004. Webseite und Preprint.
• Martin Thimm, Andrean Goede, Stefan Hougardy und Robert Preissner: Comparison of 2D Similarity and 3D Superposition. Application to Searching a Conformational Drug Database, Journal of Chemical Information and Computer Sciences, 44: 1816-1822, 2004.
• Michael Behrisch, Stefan Hougardy, Hans Jürgen Prömel, Anusch Taraz und Martin Thimm: Komplexe Netzwerke. September 2003. Poster zum Tag der offenen Tür in der Urania.
• 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, 2003. Springer. JOURNAL VERSION.
• 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, 2003. 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, 2003. Springer. JOURNAL VERSION.
• Doratha E. Drake und Stefan Hougardy: A Simple Approximation Algorithm for the Weighted Matching Problem, Information Processing Letters, 85: 211-213, 2003.
• Doratha E. Drake und Stefan Hougardy: Improved Linear Time Approximation Algorithms for Weighted Matchings. In: Sanjeev Arora, Klaus Jansen, Jose D. P. Rolim und A. Sahai (Herausgeber): Approximation, Randomization, and Combinatorial Optimization, Nummer 2764 in LNCS 2764, Seiten 14-23, 2003. Springer.
• Doratha E. Drake und Stefan Hougardy: Linear Time Local Improvements for Weighted Matchings in Graphs. In: Klaus Jansen, M. Margraf, M. Mastrolli und Jose D. P. Rolim (Herausgeber): WEA 2003, Nummer 2647 in LNCS, Seiten 107-119, 2003. Springer.
• Cornelius Frömmel, Christoph Gille, Andrean Goede, Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Robert Preissner und Martin Thimm: Accelerating screening of 3D protein data with a graph theoretical approach, Bioinformatics, 19(18): 2442-2447, 2003.
• Cornelius Frömmel, Andrean Goede, Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Robert Preissner und Martin Thimm: Accelerating screening of 3D protein data with a graph theoretical approach. April 2003. Poster zur RECOMB Berlin.
• Stefan Kirchner: Ein Approximationsalgorithmus zur Berechnung der Ähnlichkeit dreidimensionaler Punktmengen. Diplomarbeit, Humboldt-Universität zu Berlin, Institut für Informatik, September 2003.
• 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, 2002. 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, 2002. Springer. JOURNAL VERSION.
• Cornelius Frömmel, Andrean Goede, Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Robert Preissner und Martin Thimm: Accelerating screening of 3D protein data with a graph theoretical approach. November 2002. Poster zum NGFN und DHGP Symposium, Berlin.

---

zuletzt geändert am 14.07.2005 (alkox-www)