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.
More Articles
The Atomic Revolution
The 2023 Boyer Lecture series is called 'The Atomic Revolution' and is presented by Professor Michelle Simmons AO, a pioneer in atomic electronics and global leader in quantum computing.
READCelebrating excellence: Success for CQC2T at the Prime Minister’s Prize, Science Awards 2023
CQC2T Director Professor Michelle Simmons AO and Chief Investigator Professor Yuerui (Larry) Lui were recognised in the prestigious 2023 Prime Minister’s award ceremony held at Parliament House last n
READWorld Record Broken in Quantum Teleportation
An international team of researchers has developed a technology that has shattered a world record in continuous variable quantum teleportation. This latest technology offers a viable pathway enroute t
READTransversal injection for direct encoding of ancilla states for non-Clifford gates using stabilizer codes
Fault-tolerant, error-corrected quantum computation is commonly acknowledged to be crucial to the realisation of large-scale quantum algorithms that could lead to extremely impactful scientific or com
READJellybeans – a sweet solution for overcrowded circuitry in quantum computer chips
Engineers show that a jellybean-shaped quantum dot creates more breathing space in a microchip packed with qubits.
READ