Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 1/2016

01.01.2016

Efficient algorithms for cluster editing

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

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Signed Roman edge domination numbers in graphs
Nächster Artikel An efficient algorithm for distance total domination in block graphs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
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
Metadaten
Titel
Efficient algorithms for cluster editing
verfasst von
Lucas Bastos
Luiz Satoru Ochi
Fábio Protti
Anand Subramanian
Ivan César Martins
Rian Gabriel S. Pinheiro
Publikationsdatum
01.01.2016
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 1/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-014-9756-7

Weitere Artikel der Ausgabe 1/2016

Journal of Combinatorial Optimization 1/2016 Zur Ausgabe

OriginalPaper

Lower bounds on the total domination number of a graph

OriginalPaper

The blocking job shop with rail-bound transportation

OriginalPaper

An efficient algorithm for distance total domination in block graphs

OriginalPaper

Further properties on the degree distance of graphs

OriginalPaper

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

OriginalPaper

Minimum-latency aggregation scheduling in wireless sensor network

Premium Partner

    Bildnachweise