Katrin Casel

Research Interest

• Parameterized and approximation algorithms (especially in combination)
• Combinatorial optimization
• Graph theory

Teaching

At HPI:

• Communication Complexity, Master-Lecture, Winter 2021/22
• Graphenalgorithmen, Master-Lecture, Winter 2021/22
• Fault Tolerant Algorithms, Master-Project-Seminar, Summer 2021
• Exact Exponential Algorithms, Master-Lecture, Summer 2021
• Clustering in networks with more than one type of similarity, Masterproject, Winter 2020/21
• Introduction to Fine-Grained Complexity, Master-Lecture, Summer 2020
• Parameterized Algorithms, Master-Lecture, Winter 2019/20
• Asymmetries in the Travelling Salesman Problem, Masterproject, Summer 2019
• Approximation Algorithms, Master-Lecture, Winter 2018/19 & 2020/21

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

Publications

2024

•  

  Casel, Katrin; Friedrich, Tobias; Neubert, Stefan; Schmid, Markus L.Shortest distances as enumeration problemDiscrete Applied Mathematics 2024: 89–103

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Friedrich, Tobias; Niklanovits, Aikaterini; Simonov, Kirill; Zeif, ZienaCombining Crown Structures for Vulnerability MeasuresInternational Symposium on Parameterized and Exact Computation (IPEC) 2024: 1:1–1:15

  Best Paper Award

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Neubert, Stefan; Casel, KatrinIncremental Ordering for Scheduling ProblemsProceedings of the International Conference on Automated Planning and Scheduling 2024: 405–413

  [ ][ ][ URL ][ DOI ][ Download ]

2023

•  

  Behrendt, Lukas; Casel, Katrin; Friedrich, Tobias; Lagodzinski, J. A. Gregor; Löser, Alexander; Wilhelm, MarcusFrom symmetry to asymmetry: Generalizing TSP approximations by parametrizationJournal of Computer and System Sciences 2023: 157–170

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Khomutovskiy, Ivan; Dunker, Rebekka; Dierking, Jessica; Egbert, Julian; Helms, Christian; Schöllkopf, Finn; Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Isaac, Davis; Krogmann, Simon; Lenzner, PascalApplying Skeletons to Speed Up the Arc-Flags Routing AlgorithmSIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023: 110–122

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Friedrich, Tobias; Schirneck, Martin; Wietheger, SimonFair Correlation Clustering in ForestsFoundations of Responsible Computing (FORC) 2023: 9:1–9:12

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, ZienaEfficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal GraphsWorkshop Graph-Theoretic Concepts in Computer Science (WG) 2023: 143–156

  [ ][ ][ URL ][ DOI ][ Download ]

2022

•  

  Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Göbel, Andreas; Lagodzinski, J. A. GregorZeros and approximations of Holant polynomials on the complex planeComputational Complexity 2022: 11

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Fernau, Henning; Grigoriev, Alexander; Schmid, Markus L.; Whitesides, SueCombinatorial Properties and Recognition of Unit Square Visibility GraphsDiscrete & Computational Geometry 2022

  [ ][ ][ Download ]

•  

  Bilò, Davide; Casel, Katrin; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Lagodzinski, J.A. Gregor; Schirneck, Martin; Wietheger, SimonFixed-Parameter Sensitivity OraclesInnovations in Theoretical Computer Science (ITCS) 2022: 23:1–23:18

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bazgan, Cristina; Casel, Katrin; Cazals, PierreDense Graph Partitioning on sparse and dense graphs.Scandinavian Workshop Algorithm Theory (SWAT) 2022

  [ ][ ][ URL ][ DOI ][ Download ]

2021

•  

  Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, FlorianOn the Complexity of Solution Extension of Optimization ProblemsTheoretical Computer Science 2021

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.On the Complexity of the Smallest Grammar Problem over Fixed AlphabetsTheory of Computing Systems 2021: 344–409

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Borndörfer, Ralf; Casel, Katrin; Issac, Davis; Niklanovits, Aikaterini; Schwartz, Stephan; Zeif, ZienaConnected k-Partition of k-Connected Graphs and c-Claw-Free GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2021: 27:1–27:14

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, ZienaBalanced Crown Decomposition for Connectivity ConstraintsEuropean Symposium on Algorithms (ESA) 2021: 26:1–26:15

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Behrendt, Lukas; Casel, Katrin; Friedrich, Tobias; Lagodzinski, J. A. Gregor; Löser, Alexander; Wilhelm, MarcusFrom Symmetry to Asymmetry: Generalizing TSP Approximations by ParametrizationFundamentals of Computation Theory (FCT) 2021: 53–66

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Lagodzinski, J. A. Gregor; Göbel, Andreas; Casel, Katrin; Friedrich, TobiasOn Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime OrderInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 91:1–91:15

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Schmid, Markus L.Fine-Grained Complexity of Regular Path QueriesInternational Conference on Database Theory (ICDT) 2021: 19:1–19:20

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Friedrich, Tobias; Issac, Davis; Klodt, Nicolas; Seifert, Lars; Zahn, ArthurA Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved HeuristicsKnowledge Discovery and Data Mining (KDD) 2021: 882–891

  [ ][ ][ URL ][ DOI ][ Download ]

2020

•  

  Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik JanComplexity of independency and cliquy treesDiscrete Applied Mathematics 2020: 2–15

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, HenningDomination chain: Characterisation, classical complexity, parameterised complexity and approximabilityDiscrete Applied Mathematics 2020: 23–42

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bossek, Jakob; Casel, Katrin; Kerschke, Pascal; Neumann, FrankThe Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search HeuristicsGenetic and Evolutionary Computation Conference (GECCO) 2020: 1286–1294

  [ ][ ][ URL ][ DOI ][ Download ]

2019

•  

  Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, FlorianExtension of vertex cover and independent set in some classes of graphs and generalizationsInternational Conference on Algorithms and Complexity (CIAC) 2019: 124–136

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, FlorianExtension of some edge graph problems: standard and parameterized complexityFundamentals of Computation Theory (FCT) 2019: 185–200

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  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 NumberInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1–109:16

  [ ][ ][ URL ][ DOI ][ Download ]

2018

•  

  Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, HenningClustering with Lower-Bounded Sizes - A General Graph-Theoretic FrameworkAlgorithmica 2018: 2517–2550

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  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 dominationTheoretical Computer Science 2018: 2–25

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, KatrinResolving Conflicts for Lower-Bounded ClusteringInternational Symposium on Parameterized and Exact Computation (IPEC) 2018: 23:1–23:14

  [ ][ ][ URL ][ DOI ][ Download ]

2017

•  

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

  [ ][ ][ URL ][ DOI ][ Download ]

2016

•  

  Casel, Katrin; Estrada-Moreno, Alejandro; Fernau, Henning; Rodríguez-Velázquez, Juan AlbertoWeak total resolvability in graphsDiscussiones Mathematicae Graph Theory 2016: 185–210

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  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 PerspectiveAlgorithmic Aspects in Information and Management (AAIM) 2016: 113–124

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, HenningOn the Complexity Landscape of the Domination ChainAlgorithms and Discrete Applied Mathematics (CALDAM) 2016: 61–72

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.On the Complexity of Grammar-Based Compression over Fixed AlphabetsInternational Colloquium on Automata, Languages, and Programming (ICALP) 2016: 122:1–122:14

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, HenningBuilding Clusters with Lower-Bounded SizesInternational Symposium on Algorithms and Computation (ISAAC) 2016: 4:1–4:13

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  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 ApproximationInternational Workshop on Combinatorial Algorithms (IWOCA) 2016: 241–252

  [ ][ ][ URL ][ DOI ][ Download ]

2014

•  

  Casel, KatrinA Fixed-Parameter Approach for Privacy-Protection with Global RecodingFrontiers in Algorithmics (FAW) 2014: 25–35

  [ ][ ][ URL ][ DOI ][ Download ]