Computational Complexity
- Christian Komusiewicz and Johannes Uhlmann: Cluster Editing with Locally Bounded Modifications. Discrete Applied Mathematics 160(15):2259–2270, 2012.
We are interested in the design and analysis exact algorithms for NP-hard problems. To obtain efficient algorithms despite exponential worst-case running time, we follow the approach of multivariate algorithmics. Here, the idea is to identify small problem-specific parameters and design algorithms where the exponential running time part depends on only on the parameter and not on the overall instance size. Starting from a complexity analysis of a problem, our aim is to obtain exact algorithms that have low worst-case running time and are fast in practice.
We design and analyze algorithms that exploit certain problem-specific parameters and are
efficient if these parameters are small.
Laurent Bulteau
and Christian Komusiewicz:
Minimum Common String Partition Parameterized by Partition Size
is Fixed-Parameter Tractable.
In Proceedings of the 25th ACM-SIAM Symposion on Discrete Algorithms
(SODA'14).
We are interested in obtaining competetive implementations of exact algorithms for hard problems.
We employ data reduction, fixed-parameter algorithms, and integer linear programming formulations.
Sepp Hartung, Christian Komusiewicz and
André Nichterlein:
Parameterized Algorithmics and Computational
Experiments for Finding 2-Clubs.
Journal of Graph Algorithms and Applications 19(1): 155–190, 2015.
We study hard problems arising in the analysis of biological networks and in comparative genomics.
For these problems we aim to compute and evaluate exact solutions for biological real-world instances.
Sharon Bruckner,
Falk Hüffner, and
Christian Komusiewicz:
A Graph Modification Approach for Finding Core–Periphery Structures in Protein Interaction Networks.
Algorithms for Molecular Biology 10:16, 2015.
In graph clustering we want to partition a given network into cohesive subgroups,
called clusters, that interact heavily with each other and only weakly
with the other subgroups. These partitions can be used, for example, to identify functional units
of a network.
Falk Hüffner,
Christian Komusiewicz, Adrian Liebtrau, and
Rolf Niedermeier:
Partitioning Biological
Networks into Highly Connected Clusters with Maximum Edge Coverage.
IEEE/ACM Transactions on Computational Biology
and Bioinformatics 11(3): 455–467, 2014.
Clique relaxations are cohesive or dense subgraphs that can be used to identify communities in networks.
Finding large occurrences of such clique relaxations in a graph is usually hard. Our aim is to
obtain efficient algorithms for the most relevant clique relaxations.
Christian Komusiewicz:
Multivariate Algorithmics for Finding Cohesive Subnetworks.
Algorithms 9(1): 21, 2016.
We are looking for students that are interested in implementing and tuning graph
algorithms. Applicants should have a basic knowledge in algorithms and
experience in a common programming language (preferably Java or C++).
If you are interested, please contact Christian
Komusiewicz .
We are looking for bachelor and master students that are interested in algorithmic research on network and string problems. Topics range from algorithm engineering projects, where the aim is to implement and improve algorithms for a computational problem on a given set of instances to computational complexity studies where we are looking for new algorithms or algorithmic lower bounds. Two example projects are described below. Bachelor theses are usually more implementation-oriented and master theses more theory-driven but this is not a must.
Finding all connected subnetworks of a fixed size in an input network is a fundamental computational task that is a subroutine of many algorithms. Several different algorithms for this task are described in the literature but, so far, a systematic comparison is lacking. The goal of the thesis would be to implement 2–3 of these algorithms and to compare their performance on benchmark instances.
In a network, highly connected sets of nodes correspond to cohesive groups, for example groups of friends in Facebook or a protein complexes in protein interaction networks. One definition of highly connected is that at least half of the group members must be removed to disconnect the group. Finding such groups is an NP-hard problem. The aim of the project would be to find out how network properties influence the difficulty of this problem.
If you are interested in this type of topics, please contact Christian Komusiewicz . Usually, we propose 2–3 different topics; the thesis can be written in german or english.
Dr. Christian Komusiewicz
Institut für Informatik
Fakultät für Mathematik und Informatik
Friedrich-Schiller-Universität Jena
Ernst-Abbe-Platz 2
D-07743 Jena
+49 3641 946316
Room 3315