| Improved Algorithms for Bicluster Editing (2009) | |||||||||||||||
Abstract | |||||||||||||||
| 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 analysis of gene expression data. We show that by polynomial-time preprocessing, one can shrink a problem instance to one with 4k vertices, thus proving that the problem has a linear kernel, improving a quadratic kernel result. We further give a search tree algorithm that improves the running time bound from the trivial O(4 k + |E|) to O(3.24 k + |E|). Finally, we give a randomized 4-approximation, improving a known approximation with factor 11. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||