Cluster editing with vertex splitting
From MaRDI portal
Publication:1661849
DOI10.1007/978-3-319-96151-4_1zbMATH Open1403.90556arXiv1901.00156OpenAlexW2883425903MaRDI QIDQ1661849FDOQ1661849
Authors: Y. Aharonov 
Publication date: 17 August 2018
Abstract: In the Cluster Editing problem, a given graph is to be transformed into a disjoint union of cliques via a minimum number of edge editing operations. In this paper we introduce a new variant of Cluster Editing whereby a vertex can be divided, or split, into two or more vertices thus allowing a single vertex to belong to multiple clusters. This new problem, Cluster Editing with Vertex Splitting, has applications in finding correlation clusters in discrete data, including graphs obtained from Biological Network analysis. We initiate the study of this new problem and show that it is fixed-parameter tractable when parameterized by the total number of vertex splitting and edge editing operations. In particular we obtain a 4k(k + 1) vertex kernel for the problem and an search algorithm.
Full work available at URL: https://arxiv.org/abs/1901.00156
Recommendations
- Cluster editing
- Cluster editing with locally bounded modifications
- Parameterized dynamic cluster editing
- Parameterized Dynamic Cluster Editing
- Cluster editing: kernelization based on edge cuts
- Cluster editing: kernelization based on edge cuts
- Alternative parameterizations for cluster editing
- Efficient algorithms for cluster editing
- Editing graphs into disjoint unions of dense clusters
- Editing graphs into disjoint unions of dense clusters
Cited In (3)
This page was built for publication: Cluster editing with vertex splitting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661849)
