Projet 2021 Cluster Editing

AUTHOR

TA / Quyen-Linh

Optilio

optil.io

Username: QuyenLinhTA-DauphinePSL

USAGE

Execution program run with SIGTERM:

python3 main.py < file1.gr 

Execution program run without SIGTERM:

python3 all_in_one_for_optil.py < file1.gr 

RESULT DEMO (INTERATION SET = 30)

CITATION

@misc{quyenlinh2021clusterediting,
  title={Cluster Editing - Heuristic Solver},
  author={TA, Quyen-Linh},
  howpublished={\url{https://www.optil.io/optilion/}},
  username={QuyenLinhTA-DauphinePSL},
  year={2021},
  note={Repository for Cluster Editing algorithms and analysis}
}

REFERENCES

[1]. Yunlong Liu, Jianxin Wang, and Jiong Guo | An Overview of Kernelization Algorithms for Graph Modification Problems | URL : https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6867517

[2]. Gabriel Bathie - École Normale Supérieure de Lyon, France ; Nicolas Bousquet & Théo Pierron - LIRIS, CNRS, Université Claude Bernard Lyon 1, Université de Lyon, France | (Sub)linear kernels for edge modification problems towards structured graph classes

[3]. Édouard Bonnet, Florian Sikora | The Graph Motif problem parameterized by the structure of the input graph | URL: https://arxiv.org/abs/1503.05110

[4]. Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica.

[5]. Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukáš Mach, and Michał Pilipczuk. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1132–1151. SIAM, 2016.

[6]. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters

[7]. Sebastian Böcker. A golden ratio parameterized algorithm for cluster editing. Journal of Discrete Algorithms, 2012.

[8]. Robert Ganian. Using Neighborhood Diversity to Solve Hard Problems

[9]. Algorithmusentwurfstechniken für parametrisierte Graphmodifikationsprobleme - Algorithm Design Techniques for Parameterized Graph Modification Problems | URL: https://fpt.akt.tu-berlin.de/publications/theses/guo06.pdf

[10]. Erik Demaine. MIT 6.046J Design and Analysis of Algorithms, Spring 2015 | Complexity: Fixed-Parameter Algorithms | URL : https://www.youtube.com/watch?v=4q-jmGrmxKs