Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

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

Rosamond, Frances (2015). Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets. Matematica Contemporanea,44:1-12.

Document type: Journal Article
Citation counts: Google Scholar Search Google Scholar

IRMA ID 84377429xPUB69
Title Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets
Author Rosamond, Frances
Journal Name Matematica Contemporanea
Publication Date 2015
Volume Number 44
ISSN 0103-9059   (check CDU catalogue  open catalogue search in new window)
Start Page 1
End Page 12
Total Pages 12
Place of Publication Brazil
Publisher Sociedade Brasileira de Matematica
Field of Research MATHEMATICAL SCIENCES
HERDC Category C1 - Journal Article (DIISR)
Abstract The Cluster Editing problem aims to transform an undirected graph into a vertex-disjoint union of cliques by adding or deleting at most k edges. 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.
Description for Link Link to published version
URL http://mc.sbm.org.br/wp-content/uploads/sites/15/2016/02/44-2.pdf
 
Versions
Version Filter Type
Access Statistics: 5 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:55:09 CST