Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Combinatorial Optimization
Published in: Journal of Combinatorial Optimization 1/2016

01-01-2016

Efficient algorithms for cluster editing

Authors: Lucas Bastos, Luiz Satoru Ochi, Fábio Protti, Anand Subramanian, Ivan César Martins, Rian Gabriel S. Pinheiro

Published in: Journal of Combinatorial Optimization | Issue 1/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The cluster editing problem consists of transforming an input graph \(G\) into a cluster graph (a disjoint union of complete graphs) by performing a minimum number of edge editing operations. Each edge editing operation consists of either adding a new edge or removing an existing edge. In this paper we propose new theoretical results on data reduction and instance generation for the cluster editing problem, as well as two algorithms based on coupling an exact method to, respectively, a GRASP or ILS heuristic. Experimental results show that the proposed algorithms are able to find high-quality solutions in practical runtime.
previous article Signed Roman edge domination numbers in graphs
next article An efficient algorithm for distance total domination in block graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
Aiex RM, Binato S, Resende MGC (2003) Parallel grasp with path-relinking for job shop scheduling. Parallel Comput 29:393–430MathSciNetCrossRef
Bastos LO (2012) Novos algoritmos e resultados teóricos para o problema de particionamento de grafos por edição de arestas. PhD thesis, Universidade Federal Fluminense (in Portuguese)
Ben-Dor A, Shamir R, Yakhini Z (1999) Clustering gene expression patterns. J Comput Biol 6(3/4):281–297CrossRef
Böcker S, Briesemeister B, A QB, Truss A (2008) Going weighted: parameterized algorithms for cluster editing. Comb Optim Appl 5165:1–12MATH
Böcker S, Briesemeister S, Klau G (2009) Exact algorithms for cluster editing: evaluation and experiments. Algorithmica. 1–19
Dehne F, Langston MA, Luo X, Pitre S, Shaw P, Zhang Y (2006) The cluster editing problem: implementations and experiments. LNCS 4169:13–24MathSciNetMATH
Gramm J, Guo J, Hüffner F, Niedermeier R (2005) Graph-modeled data clustering: exact algorithms for clique generation. Theor Comput Sys 38:373–392CrossRefMATH
Hansen P, Mladenovic N (2003) Variable neighborhood search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics, Chap 6, Kluwer Academic Publishers, Philip Drive Norwell, MA, pp 145–183
Hartuv E, Schmitt AO, Lange J, Meier-Ewert S, Lehrach H, Shamir R (2000) An algorithm for clustering cdna fingerprints. Genomics 66(3):249–256CrossRef
Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3):264–323CrossRef
Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics, Chap 11, Kluwer Academic Publishers, Philip Drive Norwell, MA, pp 321–353
Milosavljevic A, Strezoska Z, Zeremski M, Grujic D, Paunesku T, Crkvenjakov R (1995) Clone clustering by hybridization. Genomics 27(1):83–89CrossRef
Penna PHV, Subramanian A, Ochi LS (2013) An iterated local search heuristic for the heterogeneous fleet vehiclerouting problem. J Heuristics 19(2):201–232CrossRef
Protti F, Silva MD, Szwarcfiter J (2009) Applying modular decomposition to parameterized cluster editing problems. Theory Comput Sys 44:91–104CrossRefMathSciNetMATH
Rahmann S, Wittkop T, Baumbach J, Martin M, Truss A, Böcker S (2007) Exact and heuristic algorithms for weighted cluster editing. In: Markstein P, Xu Y (eds) Comput Sys Bioinforma: CSB 2007 Conference Proceedings of the, Imp. Coll. Press, Covent Garden, London WC2H 9HE, vol 6, pp 391–400.
Resende M, Ribeiro C (2003) Greedy randomized adaptive search procedures, Chap 8, Kluwer Academic Publishers, Philip Drive Norwell MA, pp 219–249
Sen Gupta A, Palit A (1979) On clique generation using boolean equations. In: Proceedings of the IEEE. The IEEE Inc, New York. NY 10017 67:T178–180
Sharan R, Maron-Katz A, Shamir R (2003) Click and expander: a system for clustering and visualizing gene expression data. Bioinforma 19(14):1787–1799CrossRef
Souza MJF, Mine MT, de Silva MSA, Ochi LS, Subramanian A (2011) A hybrid heuristic, based on iterated local search and genius, for the vehicle routing problem with simultaneous pickup and delivery. Int J Logist Sys Manag 10(2):142–157CrossRef
Tatusov R, Fedorova N, Jackson J, Jacobs A, Kiryutin B, Koonin E, Krylov D, Mazumder R, Mekhedov S, Nikolskaya A, Rao BS, Smirnov S, Sverdlov A, Vasudevan S, Wolf Y, Yin J, Natale D (2003) The cog database: an updated version includes eukaryotes. BMC Bioinforma 4(1):41CrossRef
Wittkop T, Baumbach J, Lobo FP, Rahmann S (2007) Large scale clustering of protein sequences with FORCE: a layout based heuristic for weighted cluster editing. BMC Bioinforma 8:396CrossRef
Wittkop T, Emig D, Lange SJ, Rahmann S, Albrecht M, Morris JH, Böcker S, Stoye J, Baumbach J (2010) Partitioning biological data with transitivity clustering. Nature Methods 7(6):419–420CrossRef
Metadata
Title
Efficient algorithms for cluster editing
Authors
Lucas Bastos
Luiz Satoru Ochi
Fábio Protti
Anand Subramanian
Ivan César Martins
Rian Gabriel S. Pinheiro
Publication date
01-01-2016
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 1/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-014-9756-7

Other articles of this Issue 1/2016

Journal of Combinatorial Optimization 1/2016 Go to the issue

OriginalPaper

-labeling and integer tension of a graph embedded on torus

OriginalPaper

On the computational complexity of bridgecard

OriginalPaper

Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan

OriginalPaper

A greedy algorithm for the minimum -connected -fold dominating set problem

OriginalPaper

L(2,1)-labelings of the edge-multiplicity-paths-replacement of a graph

OriginalPaper

On the complexity of the minimum outer-connected dominating set problem in graphs

Premium Partner

    Image Credits