Proc. 2nd COCOA Enumerating Isolated Cliques in Synthetic and Financial Networks (2009)
Falk Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier
Abstract. We do computational studies concerning the enumeration of maximal isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the...
Improved Algorithms for Bicluster Editing (2009)
Jiong Guo, Falk Hüffner, Christian Komusiewicz, Yong Zhang
Abstract. The NP-hard Bicluster Editing is to add or remove at most k edges to make a bipartite graph G = (V, E) a vertex-disjoint union of complete bipartite subgraphs. It has applications in the...
Christian Komusiewicz, Johannes Uhlmann, D-jena Germany
insertionsanddeletions,intoagraphthatdoesnotcontainaninducedP5withitsfirstvertexinVt
Parameterized Algorithms and Hardness Results for Some Graph Motif Problems (2009)
Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier
Abstract. We study the NP-complete Graph Motif problem: given a vertex-colored graph G = (V, E) and a multiset M of colors, does there exist an S ⊆ V such that G[S] is connected and carries exactly...
Fixed-Parameter Algorithms for Cluster Vertex Deletion (2008)
Falk Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier
Abstract. We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one...
A Cubic-Vertex Kernel for Flip Consensus Tree (2008)
Komusiewicz, Christian, Uhlmann, Johannes
Given a bipartite graph G=(V_c,V_t,E) and a non-negative integer k, the NP-complete Minimum-Flip Consensus Tree problem asks whether G can be transformed, using up to k edge insertions and deletions,...
Fixed-Parameter Algorithms for Cluster Vertex Deletion (2008)
Falk Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier
We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches...
Various isolation concepts for the enumeration of dense subgraphs (2007)
Christian Komusiewicz, Falk Hüffner, Hannes Moser, Rolf Niedermeier
Abstract. In a graph G = (V, E), a vertex subset S ⊆ V of size k is called c-isolated if it has less than c · k outgoing edges. We repair a nontrivially flawed algorithm for enumerating all...