Algorithm engineering includes the design, the theoretical analysis, the implementation, and experimental evaluation of algorithms. This new field intends to bridge the gap between the efficient algorithms developed in algorithmic theory and the algorithms used by practitioners.
In this context, the research interests of our group focuses on algorithms, data structures, and combinatorial optimization, in particularly, for NP-hard optimization problems. The methods we use are based on exact methods like branch-and-bound, branch-and-cut, integer linear programming, polyhedral combinatorics, and graph theory on one side and heuristic techniques like local-search-based methods and evolutionary algorithms on the other.
Algorithm engineering requires thorough experimentation and evaluation of our new heuristics and exact algorithms for real problems. We have experience with a variety of applications such as graph layout problems, bioinformatics, and logistic problems such as network design.
Our central research topics are
Algorithm Engineering, in particular graph algorithms and data structures
Combinatorial Optimization, in particular for NP-hard optimization problems (ILP-based)
Graph Drawing
Network Design und Optimization
Analysis of Biological Networks and Proteomics
See also our List of active projects
Our current lectures and courses can be found at Lectures.
If you are interested in writing a diploma/Master's/Bachelor's thesis, please contact Prof. Mutzel or members of her group directly. We do not list the possible topics on this website.
An SDP Approach to Multi-level Crossing Minimization
Markus Chimani, Philipp Hungerlaender, Michael Juenger, and Petra Mutzel
ACM Journal of Experimental Algorithmics, to appear.
Scaffold Hunter - Visual Analysis of Chemical Compound Databases
Karsten Klein, Nils Kriege, and Petra Mutzel
in: International Conference on Information Visualization Theory and Applications (IVAPP) 2012, to appear.
-
Markus Chimani, Philipp Hungerlaender, Michael Juenger, and Petra Mutzel
ALENEX 2011, SIAM, 116-126
CT-Index: Fingerprint-based Graph Indexing Combining Cycles and Trees
Karsten Klein, Nils Kriege, and Petra Mutzel
Proc. 27th IEEE International Conference on Data Engineering (ICDE 2011), IEEE Computing Society, 1115-1126
Colored Simultaneous Geometric Embeddings and Universal Pointsets
Ulrik Brandes, Cesim Erten, Alejandro Estrella-Balderrama, J. Joseph Fowler, Fabrizio Frati, Markus Geyer, Carsten Gutwenger, Seok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, Giuseppe Liotta, Petra Mutzel, and Antonios Symvonis
Algorithmica 60 (3), 2011, 569-592
Upward Planarization Layout
Markus Chimani , Carsten Gutwenger, Petra Mutzel, and Hoi-Ming Wong
Journal of Graph Algorithms and Applications (JGAA) 15 (1), 2011, 127–155
An Experimental Evaluation of Multilevel Layout Methods
Bartel, G., Gutwenger, C., Klein, K., and Mutzel, P.
in: Brandes, U. (ed.), Graph Drawing 2010
Lecture Notes in Computer Science 6502, Springer-Verlag, 80-91.
Crossing Minimization and Layouts of Directed Hypergraphs with Port Constraints
Chimani, M., Gutwenger, C., Mutzel, P., Spoenemann, M., and Wong, H.-M.
in: Brandes, U. (ed.), Graph Drawing 2010
Lecture Notes in Computer Science 6502, Springer-Verlag, 141-152.
Interactive Exploration of Chemical Space with Scaffold Hunter
Wetzel, S., Klein, K., Renner, S. Rauh, D., Oprea, T.I., Mutzel, P. and Waldmann, H.
Nature Chemical Biology 5, 2009, 581-583
Graph Drawing Algorithms
Peter Eades, Carsten Gutwenger, Seok-Hee Hong, and Petra Mutzel
Chapter 6 in: M. Attallah and M. Blanton (eds.),
Algorithms and Theory of Computation Handbook,
Volume 2: Special Topics and Techniques, 2nd edition, CRC Press, 2009
Optimization in Levelled Graphs
Petra Mutzel
Part 15 in: Pardalos, P.M. und Floudas, C.A. (eds.),
Encyclopedia of Optimization, Second Edition, Springer US, 2009, 2813-2820
Inserting a Vertex into a Planar Graph
Markus Chimani, Carsten Gutwenger, Petra Mutzel, and Christian Wolf
In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, (SODA '2009), New York
ACM Press, 2009, 375-383
On open problems in biological network visualization
Albrecht, M., Kerren, A., Klein, K., Kohlbacher, O., Mutzel, P., Paul, W., Schreiber, F., and Wybrow, M.
in: Eppstein, D. und Gansner, E. (eds.), Graph Drawing 2009
Lecture Notes in Computer Science 5849, Springer-Verlag, 2010, 256-267
Port constraints in hierarchical layout of data flow diagrams
Spoenemann, M., Fuhrmann, H., Mutzel, P., and von Hanxleden, R., M.
in: Eppstein, D. und Gansner, E. (eds.), Graph Drawing 2009
Lecture Notes in Computer Science 5849, Springer-Verlag, 2010, 135-146
Upward planarization layout
Chimani, M., Gutwenger, C., Mutzel, P., and Wong, H.-M.
in: Eppstein, D. und Gansner, E. (eds.), Graph Drawing 2009
Lecture Notes in Computer Science 5849, Springer-Verlag, 2010, 94-106
Retention Time Alignment Algorithms for LC/MS Data must consider Nonlinear Shifts
Podwojski, K., Fritsch, A., Chamrad, D.C., Paul, W., Sitek, B., Stuhler, K., Stephan, C., Meyer, H.E. Urfer, W., Ickstadt, K., Rahnenführer, J.
Bioinformatics 25, 2009, 758-764
Planar Biconnectivity Augmentation With Fixed Embedding
Carsten Gutwenger, Petra Mutzel, and Bernd Zey
In: J. Kratochvil und M. Miller (eds.), 20th International Workshop on Combinatorial Algorithms, IWOCA 2009
Lecture Notes in Computer Science, Springer-Verlag, 2009, 289-300
The Crossing Number of Graphs: Theory and Computation
Petra Mutzel
in: Albers, S., Alt, H. und Näher, S. (eds.), Efficient Algorithms, Essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday
Lecture Notes in Computer Science 5760, Springer-Verlag, 2009, 305-317
