# 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 ]

- On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems 2021: 344–409
- Fine-Grained Complexity of Regular Path Queries. International Conference on Database Theory (ICDT) 2021

2020 [ nach oben ]

- Complexity of independency and cliquy trees. Discrete Applied Mathematics 2020: 2-15
- Domination chain: Characterisation, classical complexity, parameterised complexity and approximability. Discrete Applied Mathematics 2020: 23-42
- 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 ]

- Extension of vertex cover and independent set in some classes of graphs and generalizations. International Conference on Algorithms and Complexity (CIAC) 2019: 124-136
- Extension of some edge graph problems: standard and parameterized complexity. Fundamentals of Computation Theory (FCT) 2019: 185-200
- 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 ]

- Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. Algorithmica 2018: 2517-2550
- The many facets of upper domination. Theoretical Computer Science 2018: 2-25
- Resolving Conflicts for Lower-Bounded Clustering. International Symposium on Parameterized and Exact Computation (IPEC) 2018: 23:1-23:14

2017 [ nach oben ]

- 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 ]

- Weak total resolvability in graphs. Discussiones Mathematicae Graph Theory 2016: 185-210
- Algorithmic Aspects of Upper Domination: A Parameterised Perspective. Algorithmic Aspects in Information and Management (AAIM) 2016: 113-124
- On the Complexity Landscape of the Domination Chain. Algorithms and Discrete Applied Mathematics (CALDAM) 2016: 61-72
- On the Complexity of Grammar-Based Compression over Fixed Alphabets. International Colloquium on Automata, Languages, and Programming (ICALP) 2016: 122:1-122:14
- Building Clusters with Lower-Bounded Sizes. International Symposium on Algorithms and Computation (ISAAC) 2016: 4:1-4:13
- Upper Domination: Complexity and Approximation. International Workshop on Combinatorial Algorithms (IWOCA) 2016: 241-252

2014 [ nach oben ]

- A Fixed-Parameter Approach for Privacy-Protection with Global Recoding. Frontiers in Algorithmics (FAW) 2014: 25-35

# 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