# Dr. Katrin Casel

**Chair for**** Algorithm Engineering**

Hasso Plattner Institute

Office: A-1.11

Tel.: +49 331 5509-3952

E-Mail: Katrin.Casel(at)hpi.de

# Publications

2021 [ nach oben ]

- Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.
**On the Complexity of the Smallest Grammar Problem over Fixed Alphabets**Theory of Computing Systems 2021: 344–409 - Borndörfer, Ralf; Casel, Katrin; Issac, Davis; Niklanovits, Aikaterini; Schwartz, Stephan; Zeif, Ziena
**Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs**Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2021 - Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena
**Balanced Crown Decomposition for Connectivity Constraints**European Symposium on Algorithms (ESA) 2021: 26:1–26:15 - Behrendt, Lukas; Casel, Katrin; Friedrich, Tobias; Lagodzinski, J. A. Gregor; Löser, Alexander; Wilhelm, Marcus
**From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization**Fundamentals of Computation Theory (FCT) 2021: 53–66 - Lagodzinski, J. A. Gregor; Göbel, Andreas; Casel, Katrin; Friedrich, Tobias
**On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order**International Colloquium on Automata, Languages and Programming (ICALP) 2021: 91:1–91:15 - Casel, Katrin; Schmid, Markus L.
**Fine-Grained Complexity of Regular Path Queries**International Conference on Database Theory (ICDT) 2021 - Casel, Katrin; Friedrich, Tobias; Issac, Davis; Klodt, Nicolas; Seifert, Lars; Zahn, Arthur
**A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved Heuristics**Knowledge Discovery and Data Mining (KDD) 2021: 882–891

2020 [ nach oben ]

- Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik Jan
**Complexity of independency and cliquy trees**Discrete Applied Mathematics 2020: 2–15 - Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning
**Domination chain: Characterisation, classical complexity, parameterised complexity and approximability**Discrete Applied Mathematics 2020: 23–42 - Bossek, Jakob; Casel, Katrin; Kerschke, Pascal; Neumann, Frank
**The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics**Genetic and Evolutionary Computation Conference (GECCO) 2020: 1286–1294

2019 [ nach oben ]

- Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian
**Extension of vertex cover and independent set in some classes of graphs and generalizations**International Conference on Algorithms and Complexity (CIAC) 2019: 124–136 - Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian
**Extension of some edge graph problems: standard and parameterized complexity**Fundamentals of Computation Theory (FCT) 2019: 185–200 - Casel, Katrin; Day, Joel D.; Fleischmann, Pamela; Kociumaka, Tomasz; Manea, Florin; Schmid, Markus L.
**Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number**International Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1–109:16

2018 [ nach oben ]

- Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning
**Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework**Algorithmica 2018: 2517–2550 - Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.
**The many facets of upper domination**Theoretical Computer Science 2018: 2–25 - Casel, Katrin
**Resolving Conflicts for Lower-Bounded Clustering**International Symposium on Parameterized and Exact Computation (IPEC) 2018: 23:1–23:14

2017 [ nach oben ]

- Casel, Katrin; Fernau, Henning; Grigoriev, Alexander; Schmid, Markus L.; Whitesides, Sue
**Combinatorial Properties and Recognition of Unit Square Visibility Graphs**International Symposium on Mathematical Foundations of Computer Science (MFCS) 2017: 30:1–30:15

2016 [ nach oben ]

- Casel, Katrin; Estrada-Moreno, Alejandro; Fernau, Henning; Rodríguez-Velázquez, Juan Alberto
**Weak total resolvability in graphs**Discussiones Mathematicae Graph Theory 2016: 185–210 - Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.
**Algorithmic Aspects of Upper Domination: A Parameterised Perspective**Algorithmic Aspects in Information and Management (AAIM) 2016: 113–124 - Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning
**On the Complexity Landscape of the Domination Chain**Algorithms and Discrete Applied Mathematics (CALDAM) 2016: 61–72 - Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.
**On the Complexity of Grammar-Based Compression over Fixed Alphabets**International Colloquium on Automata, Languages, and Programming (ICALP) 2016: 122:1–122:14 - Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning
**Building Clusters with Lower-Bounded Sizes**International Symposium on Algorithms and Computation (ISAAC) 2016: 4:1–4:13 - Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.
**Upper Domination: Complexity and Approximation**International Workshop on Combinatorial Algorithms (IWOCA) 2016: 241–252

2014 [ nach oben ]

# Teaching

### At HPI:

- Approximation Algorithms, Master-Course, Winter 2020/21
Masterproject Clustering in networks with more than one type of similarity, Winter 2020/21

Introduction to Fine-Grained Complexity, Master-Course, Summer 2020

Parameterized Algorithms, Master-Course, Winter 2019/20

Masterproject Asymmetries in the Travelling Salesman Problem, Summer 2019

Approximation Algorithms, Master-Course, Winter 2018/19

### As teaching assistant at the University of Trier:

Parameterized Algorithms, Master-Course, Winter 2015/16

Data Compression, Master-Course, Summer 2015

Approximation Algorithms, Master-Course, Winter 2014/15 and 2016/17

Algorithms and Data Structures (as student tutor), Bachelor-Course, Summer 2009, 2010 and 2011

Mathematics for Computer Scientists, Introductory Block-Seminar, Winter 2008/09, 2010/11, 2012/13, 2013/14 and 2014/15