~~NOTOC~~ ==== Algorithm Engineering Group (Prof. Dr. Petra Mutzel) ==== ** now at University of Bonn: [[https://ca.cs.uni-bonn.de|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 ===== * [[staff:mutzel|Prof. Dr. Petra Mutzel]] * [[staff:charfreitag|Jonas Charfreitag]] * [[staff:dahn|Christine Dahn]] * [[staff:droschinsky|Andre Droschinsky]] * [[staff:jabrayilov|Adalat Jabrayilov]] * [[staff:kriege|Nils Kriege]] * [[staff:kurz|Denis Kurz]] * [[staff:morris|Christopher Morris]] * [[staff:oettershagen|Lutz Oettershagen]] * [[staff:schaefer|Till Schäfer]] * [[staff:zey|Bernd Zey]] * [[mutzel:formermembers| Former Members ]] ===== Central Research Topics of Group ===== * Algorithm Engineering, in particular graph algorithms and data structures * Combinatorial Optimization, for polynomial solvable and NP-hard optimization problems * Data Analysis and Graph Mining (Graph Similarity, Graph Kernels) * [[cheminformatics|Cheminformatics (Drug Design, Exploratory Analysis of Molecule Data Bases)]] * [[graphdrawing | Graph Drawing and Network Visualization]] * Network Analysis * Shortest Paths (multi criteria, k-best) * Network Design (Steiner tree) and Optimization ===== 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 * [[mutzel:projects| Please follow this link for the list of our projects.]] * [[http://www.ogdf.net|Open Graph Drawing Framework (OGDF)]]: A C++ library (GPL) for the automatic layout of graphs * [[http://scaffoldhunter.sourceforge.net/|Scaffold Hunter]]: A tool for the interactive exploration of chemical space ===== Teaching ===== Our current lectures and courses can be found at [[de:teaching:lectures|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 * **[[http://arxiv.org/abs/1904-11965|Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs]]** \\ // Michael Jünger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi, and Tobias Stollenwerk// \\ CoRR abs/1904-11965, 2019 * **[[https://doi.org/10.4230/LIPIcs.STACS.2019.3|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 * **[[http://arxiv.org/abs/1904.01543|Towards a practical k-dimensional Weisfeiler-Leman algorithm]]** \\ // Christopher Morris, Petra Mutzel // \\ CoRR abs/1904.01543, 2019 * **[[http://arxiv.org/abs/1903.06061|Maximum Cut Parameterized by Crossing Number]]** \\ // Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, Alexander Nover // \\ CoRR abs-1904-11965, 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 [[https://arxiv.org/abs/1812.02507| CoRR abs/1812.02507]] * **[[https://arxiv.org/abs/1806.10697|A new Integer Linear Program for the Steiner Tree Problem with Revenues, Budget and Hop Constraints]]** \\ // Adalat Jabrayilov and Petra Mutzel // \\ In: Proceedings of Algorithm Engineering & Experiments (ALENEX 2019), SIAM, 2019, to appear (also see CoRR abs/1806.10697) * **[[https://epubs.siam.org/doi/abs/10.1137/17M1147974?af=R|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 [[http://arxiv.org/abs/1510.00549 | CoRR abs/1510.00549]]) * **[[https://doi.org/10.7155/jgaa.00480| A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs]]** \\ // Nils M. Kriege, Andre Droschinsky, Petra Mutzel, Journal of Graph Algorithms and Applications// \\ vol. 22, no. 4, 607-616, 2018 * **[[https://arxiv.org/abs/1803.10983|Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs]]** \\ // Christine Dahn, Nils M. Kriege, Petra Mutzel, Julian Schilling // \\ CoRR abs/1805.06780 (and submitted to Journal) * **[[http://doi.org/10.1007/978-3-030-04414-5\_13|A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width]]** \\ // Michael Jünger, Petra Mutzel and Christine Spisla // \\ Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Lecture Notes in Computer Science 11282, Springer, 187-199, 2018 * **[[http://www.mdpi.com/2078-2489/9/7/153|More Compact Orthogonal Drawings by Allowing Additional Bends]]** \\ // Michael Jünger, Petra Mutzel and Christine Spisla // \\ Information 2018, 9 (7), MDPI, doi:10.3390/info9010001 * **Largest Weight Common Subtree Embeddings with Distance Penalties** (Preprint [[https://arxiv.org/abs/1805.00821|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 * ** [[https://arxiv.org/abs/1805.06780 | The Crossing Number of Single-Pair-Seq-Shellable Drawings of Complete Graphs ]]** \\ // Petra Mutzel, Lutz Oettershagen // \\ Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG), 11-17, 2018, also see [[https://arxiv.org/abs/1805.06780| CoRR abs/1805.06780]] * **[[http://proceedings.mlr.press/v88/|Recognizing Cuneiform Signs Using Graph Based Methods]]** (Preprint [[https://arxiv.org/abs/1802.05908|arXiv:1802.05908]]) \\ Nils M. Kriege, Matthias Fey, Denis Fisseler, Petra Mutzel, Frank Weichert \\ International Workshop on Cost-Sensitive Learning (COST), SIAM International Conference on Data Mining (SDM) 2018, Proceedings of Machine Learning Research (PMLR), vol. 88, 31-44, 2018 * ** [[https://doi.org/10.1007/978-3-319-77404-6_47 |New Integer Linear Programming Models for the Vertex Coloring Problem]]** \\ // Adalat Jabrayilov and Petra Mutzel // \\ 13th Latin American Theoretical INformatics Symposium (LATIN 2018), LNCS 10807, Springer, 640-652, 2018 * ** [[https://onlinelibrary.wiley.com/doi/epdf/10.1002/cmdc.201700689| CHIPMUNK: A virtual synthesizable small molecule library for medicinal chemistry exploitable for protein-protein interaction modulators]] ** \\ // Lina Humbeck, Sebastian Weigang, Till Schäfer, Petra Mutzel, and Oliver Koch, // \\ ChemMedChem 6/2018, vol- 13, issue 6, Very Important Paper, 532-539, 2018, doi:10.1002/cmdc.201700689; [[https://onlinelibrary.wiley.com/doi/full/10.1002/cmdc.201800126# |we also got the cover feature for this article]] * ** 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 [[https://arxiv.org/abs/1803.10983| 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 [[https://arxiv.org/abs/1803.07515| 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. * **[[http://drops.dagstuhl.de/opus/volltexte/2017/8257| 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 // * **[[http://arxiv.org/abs/1604.08147 | Tree-Deletion Pruning in Label-Correcting Algorithms for the Multiobjective Shortest Path Problem]]** \\ // Fritz Boekler and Petra Mutzel // \\ 11th International Conference and Workshop on Algorithms and Computation (WALCOM), LNCS 10167, Springer, 190-203, 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 * **[[http://arxiv.org/abs/1706.06514 | Orthogonal Compaction Using Additional Bends]]**\\ //Michael Jünger, Petra Mutzel and Christiane Spisla//, \\ CoRR abs/1706.06514, 2017, test instances available [[mutzel:compaction|here]] * ** [[https://jcheminf.springeropen.com/articles/10.1186/s13321-017-0213-3 | Scaffold Hunter: a comprehensive visual analytics framework for drug discovery]]**\\ //Till Schäfer, Nils Kriege, Lina Humbeck, Karsten Klein, Oliver Koch, Petra Mutzel // \\ Journal of Cheminformatics, vol. 9:28, no. 1, 28:1-28:18, 2017 * ** [[http://arxiv.org/abs/1610.07204 | Output-sensitive Complexity of Multiobjective Combinatorial Optimization]]**\\ //Fritz Bökler, Matthias Ehrgott, Christopher Morris, Petra Mutzel// \\ Journal of Multi-Criteria Decision Analysis, to appear 2017, CoRR abs/1610.07204, 2016 * ** [[https://doi.org/10.1007/978-3-319-51963-0_24|Finding Largest Common Substructures of Molecules in Quadratic Time]]** \\ // Andre Droschinsky, Nils Kriege and Petra Mutzel// \\ 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-FOCS 1017), LNCS 10139, Springer, 309-321, 2017 * **[[http://dx.doi.org/10.1016/j.ejor.2016.06.048|Stochastic Survivable Network Design Problems: Theory and practice]]**\\ //Ivana Ljubic, Petra Mutzel, and Bernd Zey// \\ European Journal of Operational Research (EJOR), volume 256, issue 2, pp. 333-348, 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 [[http://arxiv.org/abs/1606.01141|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 [[http://dblp.uni-trier.de/db/journals/corr/corr1601.html#KurzM16 | CoRR abs/1601.02867]] * **[[http://dblp.uni-trier.de/db/journals/corr/corr1604.html#BoklerM16 | Tree-Deletion Pruning in Label-Correcting Algorithms for the Multiobjective Shortest Path Problem]]** \\ // Fritz Boekler and Petra Mutzel // \\ CoRR abs/1604.08147, 2016 * **[[http://dx.doi.org/10.1016/j.ejor.2016.06.048 | Stochastic survivable network design problems: Theory and practice]]** \\ // Ivana Ljubic, Petra Mutzel and Bernd Zey // \\ European Journal of Operational Research, to appear 2016 * **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 * **[[http://dblp.uni-trier.de/db/conf/mfcs/mfcs2016.html#DroschinskyKM16 | Faster Algorithms for the Maximum Common Subtree Isomorphism Problem]]** \\ // Andre Droschinsky, Nils Kriege and Petra Mutzel // \\ 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs vol. 58, 33:1--33:14, 2016, also see [[http://dblp.uni-trier.de/db/journals/corr/corr1602.html#DroschinskyKM16 | CoRR abs/1602.07210]] * **On Maximum Common Subgraph Problems in Series-Parallel Graphs** \\ // Nils Kriege, Florian Kurpicz, Petra Mutzel // \\ European Journal of Combinatorics, to appear 2016 * **[[http://dblp.uni-trier.de/db/conf/esa/esa2015.html#BoklerM15 | Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems]]** \\ //Fritz Boekler, Petra Mutzel // \\ 23rd Annual European Symposium on Algorithms (ESA 2015), LNCS 9294, pp. 288-299, Springer, 2015 * **[[http://jgaa.info/issues.jsp?volume=0|Drawing Partially Embedded and Simultaneously Planar Graphs]]** \\ //Timothy Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel and Marcus Schaefer // \\ Journal on Graph Algorithms and Applications (JGAA), vol. 19, no. 2, pp. 681-706, 2015 * **[[http://arxiv.org/abs/1510.00549 | 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 // \\ CoRR http://arxiv.org/abs/1510.00549, 2015 * **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) * **[[http://dx.doi.org/10.1007/978-3-319-13075-0_7|Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay]]** \\ //Andre Droschinsky, Bernhard Heinemann, Nils Kriege and Petra Mutzel // \\ Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), LNCS 8889, Springer, 81-93 * **[[http://dx.doi.org/10.7155/jgaa.00338|Practical SAHN Clustering for Very Large Data Sets and Expensive Distance Metrics]]** \\ Nils Kriege, Petra Mutzel, Till Schäfer \\ Journal of Graph Algorithms and Applications (JGAA), vol. 18, no. 4, 577-602, 2014. * **[[http://dx.doi.org/10.1007/978-3-662-45803-7_3|Drawing Partially Embedded and Simultaneously Planar Graphs]]** \\ //Timothy Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel and Marcus Schaefer // \\ Proceedings of the 22nd International Symposium on Graph Drawing (GD 2014), LNCS 8871, Springer, 25-39 * **[[http://dblp.uni-trier.de/db/conf/iwoca/iwoca2014.html#KriegeKM14 | On Maximum Common Subgraph Problems in Series-Parallel Graphs]]** \\ // Nils Kriege, Florian Kurpicz, Petra Mutzel // \\ Proceedings of the 25th International Workshop on Combinatorial Algorithms (IWOCA 2014), Minnesota (USA), LNCS 8986, Springer, 200-212, 2014 * **[[http://ceur-ws.org/Vol-1244/GViP-paper2.pdf |Examining the Compactness of Automatically Generated Layouts for Practical Diagrams]]** \\ //Carsten Gutwenger, Reinhard von Hanxleden, Petra Mutzel, Ulf Rüegg and Miro Spönemann // \\ Proceedings of Graph Visualization in Practice (GraphViP 2014), CEUR, 42-52 * **[[http://dx.doi.org/10.1007/978-3-662-44465-8_43| Finding Maximum Common Biconnected Subgraphs in Series-Parallel Graphs]]** \\ // Nils Kriege und Petra Mutzel // \\ International Symposium on Mathematical Foundations of Computer Science (MFCS) 2014, 505-516. * **[[http://dx.doi.org/10.1007/978-3-319-04657-0_11|SAHN Clustering in Arbitrary Metric Spaces Using Heuristic Nearest Neighbor Search]]** \\ // Nils Kriege, Petra Mutzel, Till Schäfer // \\ Proceedings of the Eighth International Workshop on Algorithms and Computation (WALCOM 2014), LNCS 8344, Springer, 2014, pp. 90-101. * **[[http://dx.doi.org/10.1137/1.9781611973198.9|Practical Experience with Hanani-Tutte for Testing c-Planarity]]**\\ //Carsten Gutwenger, Petra Mutzel, and Marcus Schaefer//\\ In: Proceedings of Algorithm Engineering & Experiments (ALENEX 2014), Portland, SIAM, 2014, 86-97 * **[[http://dx.doi.org/10.1002/minf.201300087|Visual Analysis of Biological Activity Data with Scaffold Hunter]]**\\ //Karsten Klein, Oliver Koch, Nils Kriege, Petra Mutzel and Till Schäfer// \\ Molecular Informatics, WILEY-VCH Verlag, 2013 ([[http://scaffoldhunter.sourceforge.net/klein2013.bib|BIBTEX]]) * **[[http://dx.doi.org/10.1007/978-3-642-38189-8_11|The Maximum Weight Connected Subgraph Problem]]**\\ //Eduardo Alvarez-Miranda, Ivana Ljubic, Petra Mutzel \\ // Bookchapter in: M. Jünger and G. Reinelt, Facets of Combinatorial Optimization, Springer, 2013, pp. 245-270. * **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. * **[[http://dx.doi.org/10.1007/978-3-642-38171-3_20|The Rooted Maximum Node-Weight Connected Subgraph Problem]]**\\ //Eduardo Alvarez-Miranda, Ivana Ljubic, Petra Mutzel \\ // 10th Intern. Conf. on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2013), pp. 300-315 * **[[http://www.sciencedirect.com/science/article/pii/S1571065313001029|Stochastic Survivable Network Design Problems]]**\\ //Ivana Ljubic, Petra Mutzel, and Bernd Zey// \\ International Network Optimization Conference (INOC) \\ Electronic Notes in Discrete Mathematics (ENDM), 2013, pp.245-252 * ** [[http://dx.doi.org/10.1007/s00287-013-0682-3|Algorithm Engineering im Graphenzeichnen]]** \\ //Martin Gronemann, Carsten Gutwenger, Michael Jünger, and Petra Mutzel //\\ Hauptbeitrag in Informatik Spektrum, vol. 36, no. 2, Springer, 2013, pp. 162-173 * ** [[http://example.com|MolMap - Visualizing Molecule Libraries as Topographic Maps]]** \\ // Martin Gronemann, Michael Jünger, Nils Kriege, Petra Mutzel //\\in: International Conference on Information Visualization Theory and Applications (IVAPP, best paper award), 2013, pp. 515-524 * **[[http://link.springer.com/chapter/10.1007%2F978-3-642-36046-6_14|Parameterized Algorithms for Stochastic Steiner Tree Problems]]** \\ //Denis Kurz, Petra Mutzel, and Bernd Zey// \\ Mathematical and Engineering Methods in Computer Science (MEMICS 2012) \\ Lecture Notes in Computer Science 7721, Springer-Verlag, 2013, pages 143--154 * **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 * **[[http://siam.omnibooksonline.com/2012ALENEX/ |Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, ALENEX 2012]]** \\ // David Bader, Petra Mutzel (Eds.) //\\ ALENEX 2012, The Westin Miyako, Kyoto, SIAM Omnipress, 2012 * **[[http://icml.cc/discuss/2012/542.html|Subgraph Matching Kernels for Attributed Graphs]]** \\ //Nils Kriege and Petra Mutzel\\ // 29th International Conference on Machine Learning (ICML), Edinburgh, Scotland, International Machine Learning Society, 2012 * **[[http://dx.doi.org/10.1016/j.jda.2012.04.016|Improved Steiner Tree Algorithms for Bounded Treewidth]]**\\ //Markus Chimani, Petra Mutzel, and Bernd Zey// \\ Journal of Discrete Algorithms, vol. 16, 2012, pp. 67-78. * ** 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. * **[[http://dx.doi.org/10.1016/j.ejc.2011.09.009|Vertex insertion approximates the crossing number of apex graphs]]**\\ //Markus Chimani, Petr Hlineny and Petra Mutzel//\\ in: European Journal of Combinatorics, vol. 33 (3), 2012, pp. 326-335. * **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. * **[[http://www.springerlink.com/content/p426735723444527/|Improved Steiner Tree Algorithms for Bounded Treewidth]]**\\ //Markus Chimani, Petra Mutzel, and Bernd Zey// \\ International Workshop on Combinatorial Algorithms (IWOCA 2011) \\ Lecture Notes in Computer Science 7056, Springer-Verlag, 2011, pp. 374-386. * **[[http://www.siam.org/proceedings/alenex/2011/alx11_12_chimanim.pdf|An SDP Approach to Multi-level Crossing Minimization]]**\\ * //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 * **[[http://doi.acm.org/10.1007/s00453-010-9433-x|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 * **[[http://dx.doi.org/10.4230/DagRep.1.5.47|Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191)]]**\\ //Camil Demetrescu, Michael Kaufmann, Stephen G. Kobourov, Petra Mutzel //\\ Dagstuhl Reports 1 (5), 2011, 47-60 * **[[http://www.springerlink.com/content/74n3181l41202406/|Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut]]**\\ //Immanuel Bomze, Markus Chimani, Michael Jünger, Ivana Ljubic, Petra Mutzel, and Bernd Zey//\\ Proc. 21st Int. Symp. on Algorithms and Computation (ISAAC 2010)\\ Lecture Notes in Computer Science 6506, Springer-Verlag, 2010, 427-439. * **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. * **[[http://doi.acm.org/10.1145/1671973.1671975|Layer-Free Upward Crossing Minimization]]**\\ //Markus Chimani , Carsten Gutwenger, Petra Mutzel, and Hoi-Ming Wong//\\ ACM Journal of Experimental Algorithmics 15, Article No. 2.2, 2010 * **[[http://dx.doi.org/10.1007/s10107-010-0375-5|Oriented-based models for {0,1,2}-survivable network design: theory and practice]]**\\ //Markus Chimani, Maria Kandyba, Ivana Ljubic, and Petra Mutzel//\\ Mathematical Programming B, vol. 124, no. 1-2, 2010, 413-439 * **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.), [[http://www.crcpress.com/product/isbn/9781584888185|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.), [[http://doi.acm.org/10.1007/978-0-387-74759-0_483|Encyclopedia of Optimization]], Second Edition, Springer US, 2009, 2813-2820 * **[[http://doi.acm.org/10.1145/1498698.1537600|Obtaining Optimal k-Cardinality Trees Fast]]**\\ //Markus Chimani, Maria Kandyba, Ivana Ljubic, and Petra Mutzel//\\ ACM Journal of Experimental Algorithmics (JEA), vol. 14 (2), 2009, 5.1-5.23 * **[[http://www.siam.org/proceedings/soda/2009/SODA09_042_chimanim.pdf|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 * **[[http://doi.acm.org/10.1145/1498698.1564504|Experiments on Exact Crossing Minimization using Column Generation]]**\\ //Markus Chimani, Carsten Gutwenger, and Petra Mutzel//\\ ACM Journal of Experimental Algorithmics (JEA), vol. 14 (4), 2009, 4.1-4.18 * **[[http://dx.doi.org/10.1007/978-3-642-02882-3_25|On the Hardness and Approximability of Planar Biconnectivity Augmentation]]**\\ //Carsten Gutwenger, Petra Mutzel, and Bernd Zey//\\ In: H. Q. Ngo (ed.), 15th Annual International Computing and Combinatorics Conference, COCOON 2009\\ Lecture Notes in Computer Science 5609, Springer-Verlag, 2009, 249-257 * **[[http://dx.doi.org/10.1007/978-3-642-11805-0_25|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 * **[[http://dx.doi.org/10.1007/978-3-642-11805-0_14|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 * **[[http://dx.doi.org/10.1007/978-3-642-11805-0_11|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 * **[[http://dx.doi.org/10.1093/bioinformatics/btp052|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 * **[[http://dx.doi.org/10.1007/978-3-642-10217-2_29|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 * **[[http://dx.doi.org/10.1007/978-3-642-03456-5|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