Christian Komusiewicz

Christian Komusiewicz

orcid

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 October 2008 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
FHFalk Hüffner
Falk Hüffner
CKChristian Komusiewicz
Christian Komusiewicz
HMHannes Moser
Hannes Moser
RNRolf Niedermeier
Rolf Niedermeier

1 October 2012 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
CKChristian Komusiewicz
Christian Komusiewicz
JUJohannes Uhlmann
Johannes Uhlmann

4 February 2011 in IEEE/ACM Transactions on Computational Biology and Bioinformatics
Verified
Journal Article
Closed access
NBNadja Betzler
Nadja Betzler
RBRene van Bevern
Rene van Bevern
MFMichael R. Fellows
Michael R. Fellows
CKChristian Komusiewicz
Christian Komusiewicz
RNRolf Niedermeier
Rolf Niedermeier
We study the NP-hard LIST-COLORED GRAPH MOTIF problem which, given an undirected list-colored graph G = (V, E) and a multiset M of colors, asks for maximum-cardinality sets S ⊆ V and M' ⊆ M such that G[S] is connected and contains exactly (with respect to multiplicity) the colors in M'. LIST-COLORED GRAPH MOTIF has applications in the analysis of biological networks. We study LIST-COLORED GRAPH MOTIF with respect to three different parameterizations. For the parameters motif size |M| and solution size |S|, we present fixed-parameter algorithms, whereas for the parameter |V| - |M|, we show W[1]-hardness for general instances and achieve fixed-parameter tractability for a special case of LIST-COLORED GRAPH MOTIF. We implemented the fixed-parameter algorithms for parameters |M| and |S|, developed further speed-up heuristics for these algorithms, and applied them in the context of querying protein-interaction networks, demonstrating their usefulness for realistic instances. Furthermore, we show that extending the request for motif connectedness to stronger demands, such as biconnectedness or bridge-connectedness leads to W[1]-hard problems when the parameter is the motif size |M|.

5 April 2011 in Optimization Letters
Verified
Journal Article
Closed access
PDF file
ASAlexander Schäfer
Alexander Schäfer
CKChristian Komusiewicz
Christian Komusiewicz
HMHannes Moser
Hannes Moser
RNRolf Niedermeier
Rolf Niedermeier

1 February 2011 in Discrete Optimization
Verified
Journal Article
Closed access
MFMichael R. Fellows
Michael R. Fellows
JGJiong Guo
Jiong Guo
CKChristian Komusiewicz
Christian Komusiewicz
RNRolf Niedermeier
Rolf Niedermeier
JUJohannes Uhlmann
Johannes Uhlmann

16 March 2016 in Algorithms
Verified
Journal Article
Open access
PDF file
CKChristian Komusiewicz
Christian Komusiewicz
Community detection is an important task in the analysis of biological, social or technical networks. We survey different models of cohesive graphs, commonly referred to as clique relaxations, that are used in the detection of network communities. For each clique relaxation, we give an overview of basic model properties and of the complexity of the problem of finding large cohesive subgraphs under this model. Since this problem is usually NP-hard, we focus on combinatorial fixed-parameter algorithms exploiting typical structural properties of input networks.