Editing to Cliques

A Survey of FPT Results and Recent Applications in Analyzing Large Datasets

Frances Rosamond

Research output: Contribution to journal › Article › Research › peer-review

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

Parameterization

Cite this

Rosamond, Frances. / Editing to Cliques : A Survey of FPT Results and Recent Applications in Analyzing Large Datasets. In: Matematica Contemporanea. 2016 ; Vol. 44, No. 1-2. pp. 1-12.
@article{50ec805891664060a2be8022ee9ad667,
title = "Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets",
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.",
author = "Frances Rosamond",
year = "2016",
language = "English",
volume = "44",
pages = "1--12",
journal = "Matematica Contemporanea",
issn = "0103-9059",
publisher = "Sociedade Brasileira de Matematica",
number = "1-2",

}

Rosamond, F 2016, 'Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets', Matematica Contemporanea, vol. 44, no. 1-2, pp. 1-12.

Editing to Cliques : A Survey of FPT Results and Recent Applications in Analyzing Large Datasets. / Rosamond, Frances.

In: Matematica Contemporanea, Vol. 44, No. 1-2, 2016, p. 1-12.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - Editing to Cliques

T2 - A Survey of FPT Results and Recent Applications in Analyzing Large Datasets

AU - Rosamond, Frances

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

M3 - Article

VL - 44

SP - 1

EP - 12

JO - Matematica Contemporanea

JF - Matematica Contemporanea

SN - 0103-9059

IS - 1-2

ER -

Rosamond F. Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets. Matematica Contemporanea. 2016;44(1-2):1-12.

Access to Document