You are here:: TU Dortmund > Department of Computer Science > Chair 11: ALGORITHM ENGINEERING > Algorithm Engineering Group (Prof. Dr. Petra Mutzel)
 

Algorithm Engineering Group (Prof. Dr. Petra Mutzel)

now at University of Bonn: Computational Analytics at Bonn University

Overview

Algorithm engineering includes the design, the theoretical analysis, the implementation, and experimental evaluation of algorithms. This field intends to bridge the gap between the efficient algorithms developed in algorithmic theory and the algorithms used by practitioners.

Algorithm engineering in combination with optimization and modern methods from machine learning is the basis for successful research in computational analytics and algorithmic data analysis.

In this context, the research interests of our group focuses on algorithms, data structures, and combinatorial optimization, for polynomial and NP-hard optimization problems on graphs and networks. The methods we use are based on exact methods like efficient graph algorithms, machine learning approaches, decomposition methods, structural studies, branch-and-bound, branch-and-cut, integer linear programming, polyhedral combinatorics, and graph theory on one side and approximation techniques like randomisation, sampling, local-search-based methods and evolutionary algorithms on the other. In particular, big data challenges are tackled via randomised, sampling or decomposition approaches that at the same time guarantee some (expected) approximation.

Algorithm engineering requires thorough experimentation and evaluation of our new algorithms for real problems. We have experience with a variety of applications such as graph (network) visualisation problems, cheminformatics (drug design), bioinformatics, archeology, statistical physics, and logistic problems such as network design and optimization.

Group

Central Research Topics of Group

Projects and Software Development (Currently)

  • DFG SFB 876: Resource-efficient Graph Mining
  • DFG GRK 1855: Discrete Optimization of Technical Systems Under Uncertainty
  • DFG SPP 1736: Graph-Based Methods for Rational Drug Design
  • DFG: Compact Drawing with Port Constraints
  • BMWi: Bewertung und Planung von Stromnetzen
  • Please follow this link for the list of our 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

  • A unifying view of explicit and implicit feature maps of graph kernels
    Nils M. Kriege, Marion Neumann, Christopher Morris, Kristian Kersting, and Petra Mutzel
    Data Mining and Knowledge Discovery, 2019, to appear
  • Algorithmic Data Science (Invited Talk)
    Petra Mutzel
    36th International Symposium on Theoretical Aspects of Computer Science, (STACS) 2019, Eds. R. Niedermeier and C. Paul, LIPIcs vol. 126, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 3:1–3:15, 2019
  • On the Enumeration of Bicriteria Temporal Paths
    Lutz Oettershagen and Petra Mutzel
    Theory and Applications of Models of Computation (TAMC 2019), LNCS 11436, Springer, to appear 2019, also see CoRR abs/1812.02507
  • Bishellable drawings of Kn
    Bernardo M. Abrego, Oswin Aichholzer, Silvia Fernandez-Merchant, Dan McQuillan, Bojan Mohar, Petra Mutzel, Pedro Ramos, R. Bruce Richter, and Birgit Vogtenhuber
    SIAM Journal on Discrete Mathematics, vol. 32, no. 4, 482–2492, 2018 (preprint see CoRR abs/1510.00549)
  • Largest Weight Common Subtree Embeddings with Distance Penalties (Preprint arXiv:1805.00821)
    Andre Droschinsky, Nils M. Kriege, Petra Mutzel
    43rd International Symposium on Mathematical Foundations of Computer Science (MFCS) 2018, LIPIcs, vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 54:1-54:15, 2018
  • The Crossing Number of Seq-Shellable Drawings of Complete Graphs
    Petra Mutzel, Lutz Oettershagen
    International Workshop on Combinatorial Algorithms 2018, IWOCA 2018, Lecture Notes in Computer Science 10979, 273-284 (also see CoRR abs/1803.10983)
  • A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs
    Christine Dahn, Nils M. Kriege, Petra Mutzel
    29th International Workshop on Combinatorial Algorithms 2018, IWOCA 2018, Lecture Notes in Computer Science 10979, 141-152 (also see CoRR abs/1803.07515)
  • On Maximum Common Subgraph Problems in Series-Parallel Graphs
    Nils Kriege, Florian Kurpicz, Petra Mutzel
    European Journal of Combinatorics, Elsevier, vol. 68, 75-95, 2018
  • Orthogonal Compaction Using Additional Bends
    M. Jünger, P. Mutzel and C. Spisla
    Proc. of the 13th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP) 2018, vol. 3: IVAPP, SciTePress, 144-155, 2018
  • Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs
    Christopher Morris, Kristian Kersting, and Petra Mutzel
    IEEE International Conference on Data Mining (ICDM 2017), New Orleans, LA, USA, pp. 327–336, IEEE Computer Society, 2017.
  • 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
  • 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: 2020-02-19 18:07 (external edit)
DokuWiki — RSS-Feed —
Barrierefreiheit   Datenschutzerklärung   Impressum