Computational Analytics

People: Christine Dahn

An algorithm is called fixed parameter tractable (short: FPT) if its running time can be decomposed as follows: f(k) · n^c, where n is the size of the input (e.g. number of nodes/ edges of a graph), k is a parameter, which depends on the input (typically either the size of the solution sought after, or a number describing how structured the input instance is, e.g. crossing number or treewidth), f(.) is a computable function, and c is a constant. The overall goal in parameterized algorithmics is to develop fixed parameter tractable algorithms for a given problem with a specific parameter k, and to improve thereon by lowering the factor f(k) and/or the constant c.

• Christine Dahn, Nils M. Kriege, Petra Mutzel, Julian Schilling: Fixed-parameter algorithms for the weighted Max-Cut problem on embedded 1-planar graphs.
  Theoretical Computer Science 852: 172-184 (2021). (arxiv)
  

• Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, Alexander Nover:Maximum Cut Parameterized by Crossing Number.
  Journal of Graph Algorithms and Applications 24(3): 155-170 (2020). (arxiv)