Skip to main content
Erschienen in: Journal of Combinatorial Optimization 1/2017

19.07.2016

Parameterized algorithms for min–max 2-cluster editing

verfasst von: Li-Hsuan Chen, Bang Ye Wu

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

Einloggen

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

search-config
loading …

Abstract

For a given graph and an integer t, the MinMax 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
Zurück zum Zitat Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: Ranking and clustering. J ACM 55(5):231:23–27 Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: Ranking and clustering. J ACM 55(5):231:23–27
Zurück zum Zitat Böcker S, Briesemeister S, Bui Q, Truss A (2009) Going weighted: parameterized algorithms for cluster editing. Theoret Comput Sci 410(52):5467–5480MathSciNetCrossRefMATH Böcker S, Briesemeister S, Bui Q, Truss A (2009) Going weighted: parameterized algorithms for cluster editing. Theoret Comput Sci 410(52):5467–5480MathSciNetCrossRefMATH
Zurück zum Zitat Bonizzoni P, Vedova GD, Dondi R (2009) A PTAS for the minimum consensus clustering problem with a fixed number of clusters. In: Eleventh Italian Conference on Theoretical Computer Science Bonizzoni P, Vedova GD, Dondi R (2009) A PTAS for the minimum consensus clustering problem with a fixed number of clusters. In: Eleventh Italian Conference on Theoretical Computer Science
Zurück zum Zitat Bonizzoni P, Vedova GD, Dondi R, Jiang T (2008) On the approximation of correlation clustering and consensus clustering. J Comput Syst Sci 74(5):671–696MathSciNetCrossRefMATH Bonizzoni P, Vedova GD, Dondi R, Jiang T (2008) On the approximation of correlation clustering and consensus clustering. J Comput Syst Sci 74(5):671–696MathSciNetCrossRefMATH
Zurück zum Zitat Chen LH, Chang MS, Wang CC, Wu BY (2013) On the min–max 2-cluster editing problem. J Inf Sci Eng 29:1109–1120MathSciNet Chen LH, Chang MS, Wang CC, Wu BY (2013) On the min–max 2-cluster editing problem. J Inf Sci Eng 29:1109–1120MathSciNet
Zurück zum Zitat Damaschke P (2009) Bounded-degree techniques accelerate some parameterized graph algorithms. In: Chen J, Fomin F (eds) Parameterized and exact computation, vol 5917., Lecture Notes in Computer ScienceSpringer, Berlin, pp 98–109CrossRef Damaschke P (2009) Bounded-degree techniques accelerate some parameterized graph algorithms. In: Chen J, Fomin F (eds) Parameterized and exact computation, vol 5917., Lecture Notes in Computer ScienceSpringer, Berlin, pp 98–109CrossRef
Zurück zum Zitat Fellows MR, Guo J, Komusiewicz C, Niedermeier R, Uhlmann J (2011) Graph-based data clustering with overlaps. Discrete Optim 8(1): 2–17 (Parameterized Complexity of Discrete Optimization) Fellows MR, Guo J, Komusiewicz C, Niedermeier R, Uhlmann J (2011) Graph-based data clustering with overlaps. Discrete Optim 8(1): 2–17 (Parameterized Complexity of Discrete Optimization)
Zurück zum Zitat Filkov V, Skiena S (2004) Integrating microarray data by consensus clustering. Int J Artif Intell Tools 13(04):863–880CrossRefMATH Filkov V, Skiena S (2004) Integrating microarray data by consensus clustering. Int J Artif Intell Tools 13(04):863–880CrossRefMATH
Zurück zum Zitat Finney RL, Weir WD, Giordano FR (2001) Thomas’ calculus, vol 10. Addison-Wesley, Reading Finney RL, Weir WD, Giordano FR (2001) Thomas’ calculus, vol 10. Addison-Wesley, Reading
Zurück zum Zitat Fomin FV, Kratsch S, Pilipczuk M, Pilipczuk M, Villanger Y (2014) Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J Comput Syst Sci 80(7):1430–1447MathSciNetCrossRefMATH Fomin FV, Kratsch S, Pilipczuk M, Pilipczuk M, Villanger Y (2014) Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J Comput Syst Sci 80(7):1430–1447MathSciNetCrossRefMATH
Zurück zum Zitat Gramm J, Guo J, Hüffner F, Niedermeier R (2005) Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput Syst 38(4):373–392MathSciNetCrossRefMATH Gramm J, Guo J, Hüffner F, Niedermeier R (2005) Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput Syst 38(4):373–392MathSciNetCrossRefMATH
Zurück zum Zitat Gramm J, Guo J, Hüffner F, Niedermeier R (2004) Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39:321–347MathSciNetCrossRefMATH Gramm J, Guo J, Hüffner F, Niedermeier R (2004) Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39:321–347MathSciNetCrossRefMATH
Zurück zum Zitat Hüffner F, Komusiewicz C, Moser H, Niedermeier R (2010) Fixed-parameter algorithms for cluster vertex deletion. Theory Comput Syst 47:196–217MathSciNetCrossRefMATH Hüffner F, Komusiewicz C, Moser H, Niedermeier R (2010) Fixed-parameter algorithms for cluster vertex deletion. Theory Comput Syst 47:196–217MathSciNetCrossRefMATH
Zurück zum Zitat Kováč I, Selečéniová I, Steinová M (2014) On the clique editing problem. In: Csuhaj-Varjú E, Dietzfelbinger M, Ésik Z (eds) Mathematical foundations of computer science 2014, vol 8635., Lecture notes in computer scienceSpringer, Berlin, pp 469–480 Kováč I, Selečéniová I, Steinová M (2014) On the clique editing problem. In: Csuhaj-Varjú E, Dietzfelbinger M, Ésik Z (eds) Mathematical foundations of computer science 2014, vol 8635., Lecture notes in computer scienceSpringer, Berlin, pp 469–480
Zurück zum Zitat Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, CambridgeCrossRefMATH Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, CambridgeCrossRefMATH
Zurück zum Zitat Wu BY, Chen LH (2015) Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions. Algorithmica 72:818–835MathSciNetCrossRefMATH Wu BY, Chen LH (2015) Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions. Algorithmica 72:818–835MathSciNetCrossRefMATH
Metadaten
Titel
Parameterized algorithms for min–max 2-cluster editing
verfasst von
Li-Hsuan Chen
Bang Ye Wu
Publikationsdatum
19.07.2016
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 1/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-016-0059-z

Weitere Artikel der Ausgabe 1/2017

Journal of Combinatorial Optimization 1/2017 Zur Ausgabe