Algorithm Engineering (Prof. Mutzel)

Overview

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, chem- and bioinformatics, and logistic problems such as network design.

Group

Research and Projects

Our Central Research Topics

  • Algorithm Engineering, in particular graph algorithms and data structures
  • Combinatorial Optimization, in particular for NP-hard optimization problems (ILP-based)
  • Network Design und Optimization

Software Development

See also our exhaustive List of active projects

Teaching

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.

Selected Recent Publications

  • New Integer Linear Programming Models for the Vertex Coloring Problem
    Adalat Jabrayilov and Petra Mutzel
    13th Latin American Theoretical INformatics Symposium (LATIN 2018), LNCS, Springer, to appear
  • Orthogonal Compaction Using Additional Bends
    M. Jünger, P. Mutzel and C. Spisla
    Proc. of the 9th International Conference on Information Visualization Theory and Applications (IVAPP 2018), to appear
  • Crossing Number for Graphs with Bounded Pathwidth
    Therese Biedl, Markus Chimani, Martin Derka and Petra Mutzel
    28th International Symposium on Algorithms and Computation (ISAAC 2017), eds. Y. Okamoto and T. Tokuyama, Leibniz International Proceedings in Informatics (LIPIcs), volume 92, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 13:1–13:13, 2017.
  • Erratum to: A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
    Nils M. Kriege, A. Droschinsky, P. Mutzel
  • On Maximum Common Subgraph Problems in Series-Parallel Graphs
    Nils Kriege, Florian Kurpicz, Petra Mutzel
    European Journal of Combinatorics, Elsevier, to appear 2017
  • A Unifying View of Explicit and Implicit Feature Maps for Structured Data: Systematic Studies of Graph Kernels
    Nils M. Kriege, Marion Neumann, Christopher Morris, Kristian Kersting, and Petra Mutzel
    CoRR abs/1703.00676, 2017
  • Faster Kernels for Graphs with Continuous Attributes via Hashing
    Christopher Morris, Nils M. Kriege, Kristian Kersting, and Petra Mutzel
    IEEE International Conference on Data Mining series (ICDM) 2016, to appear 2016
  • On Valid Optimal Assignment Kernels and Applications to Graph Classification
    Nils M. Kriege, Pierre-Louis Giscard, Richard C. Wilson
    Advances in Neural Information Processing Systems (NIPS) 2016, to appear 2016, also see arXiv:1606.01141
  • A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph
    Denis Kurz and Petra Mutzel
    The 27th International Symposium on Algorithms and Computation (ISAAC 2016), to appear 2016, also see CoRR abs/1601.02867
  • Matheuristics for optimizing the network in German wagonload traffic
    Julia Sender, Thomas Siwczyk, Petra Mutzel, Uwe Clausen
    EURO Journal on Computational Optimization, to appear 2016
  • Compact Layered Drawings of General Directed Graphs
    Adalat Jabrayilov, Sven Mallach, Petra Mutzel, Ulf Rüegg and Reinhard von Hanxleden
    Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016), to appear 2016
  • On Maximum Common Subgraph Problems in Series-Parallel Graphs
    Nils Kriege, Florian Kurpicz, Petra Mutzel
    European Journal of Combinatorics, to appear 2016
  • Explicit Versus Implicit Graph Feature Maps: A Computational Phase Transition for Walk Kernels
    Nils Kriege, Marion Neumann, Kristian Kersting, Petra Mutzel
    2014 IEEE International Conference on Data Mining (ICDM 2014), 881-886
  • Scaffold hunter: visual analysis of biological activity data
    Karsten Klein, Oliver Koch, Nils Kriege, Petra Mutzel, Till Schäfer
    J. Cheminformatics 6(S-1): 33 (2014)
  • Crossings and Planarization
    Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger and Petra Mutzel
    Bookchapter in: R. Tamassia (ed.), Graph Drawing and Visualization, CRC Press, 2014, pp. 43-85.
  • The Open Graph Drawing Framework (OGDF)
    Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein and Petra Mutzel
    Bookchapter in: R. Tamassia (ed.), Graph Drawing and Visualization, CRC Press, 2014, 543-569.
  • The Stochastic Steiner Tree Problem on Partial k-Trees
    Fritz Bökler, Petra Mutzel and Bernd Zey,
    Proc. Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS) 2012, NOVPRESS Brno, October 2012
  • Scaffold Hunter - Visual Analysis of Chemical Compound Databases
    Karsten Klein, Nils Kriege, and Petra Mutzel
    in: GRAPP & IVAPP 2012: Proc. International Conference on Computer Graphics Theory and Applications and International Conference on Information Visualization Theory and Applications, Rome, Italy, SciTePress, 2012, pp. 626-635.
  • An SDP Approach to Multi-level Crossing Minimization
    Markus Chimani, Philipp Hungerlaender, Michael Juenger, and Petra Mutzel
    ACM Journal of Experimental Algorithmics, vol. 17, no. 1, 2011.
  • 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
  • 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
  • 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
 
Last modified: 2017-12-07 14:09 by Petra Mutzel
DokuWikiRSS-Feed