Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets

Frances Rosamond

Research output: Contribution to journalArticle

Abstract

The Cluster Editing problem aims to transform an undirected graph into a vertex-disjoint union of cliques by adding or deleting at most kedges. It has been proven NP-hard several times as it has been discovered and rediscovered in important application areas. Most biologists, social scientists and other practitioners have databases and networks that need clustering. This paper describes four approaches to more realistically model what is found in practice: 1) Parameterized Complexity, kernelization, and the Cluster Editing Crown Reduction Rule, 2) Bigger, more aggressive, aggregate parameterization, 3) Fuzzy Cluster Editing and moving approximation into the modeling, and 4) Working “bottom-up” uniting kernelization and heuristics. Some applications are discussed.
Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalMatematica Contemporanea
Volume44
Issue number1-2
Publication statusPublished - 2016
Externally publishedYes

Fingerprint Dive into the research topics of 'Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets'. Together they form a unique fingerprint.

  • Cite this