Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

A new polynomial class of cluster deletion problem

,

DOI: http://dx.doi.org/10.15439/2016F273

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 585–590 ()

Full text

Abstract. Cluster Deletion (CD) problem asks to transform a given graph into a cluster graph by at most k edge deletions. CD is a combinatorial problem arising in the field of classification. In this paper, we introduce a graph transformation which enabled the identification of new polynomially solvable classes of CD problem. We show that if a graph is K3-free or (diamond, kite, house, xbanner)-free then cluster deletion problem can be solved in polynomial time on that graph.

References

  1. M. Azad and M. Moshkov, “Classification and optimization of decision trees for inconsistent decision tables represented as MVD tables,” in 2015 Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Łódz, Poland, September 13-16, 2015, 2015, pp. 31–38. [Online]. Available: http://dx.doi.org/10.15439/2015F231
  2. R. Ziembinski, “Unsupervised extraction of graph-stream structure for purpose of knowledge retrieval and information fusion,” in Position Papers of the 2015 Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Lódz, Poland, September 13-16, 2015., 2015, pp. 53–60. [Online]. Available: http://dx.doi.org/10.15439/2015F288
  3. C.-T. Cheng, C. K. Tse, and F. C. M. Lau, “A clustering algorithm for wireless sensor networks based on social insect colonies,” IEEE Sensors Journal, pp. 711–721, 2010. [Online]. Available: http://dx.doi.org/10.1109/JSEN.2010.2063021
  4. C. S. Nam, Y. S. Han, and D. R. Shin, “Multi-hop routing-based optimization of the number of cluster-heads in wireless sensor networks,” Sensors Journal, pp. 2875–2884, 2011. [Online]. Available: http://dx.doi.org/10.3390/s110302875
  5. N. Amini, A. Vahdatpour, W. Xu, M. Gerla, and M. Sarrafzadeh, “Cluster size optimization in sensor networks with decentralized clusterbased protocols.” Computer Communications, pp. 207–220, 2012. [Online]. Available: http://dx.doi.org/10.1016/j.comcom.2011.09.009
  6. J. Cong and S. K. Lim, “Edge separability-based circuit clustering with application to multilevel circuit partitioning,” IEEE Trans. on CAD of Integrated Circuits and Systems, pp. 346–357, 2004. [Online]. Available: http://dx.doi.org/10.1109/TCAD.2004.823353
  7. R. Shamir, R. Sharan, and D. Tsur, “Cluster graph modification problems,” Discrete Applied Mathematics, pp. 173–182, 2004. [Online]. Available: http://dx.doi.org/10.1016/j.dam.2004.01.007
  8. F. Bonomo, G. Durán, and M. Valencia-Pabon, “Complexity of the cluster deletion problem on subclasses of chordal graphs,” Theor. Comput. Sci., pp. 59–69, 2015. [Online]. Available: http://dx.doi.org/10.1016/j.tcs.2015.07.001
  9. Y. Gao, D. R. Hare, and J. Nastos, “The cluster deletion problem for cographs,” Discrete Mathematics, pp. 2763–2771, 2013. [Online]. Available: http://dx.doi.org/10.1016/j.disc.2013.08.017
  10. F. Bonomo, G. Durán, A. Napoli, and M. Valencia-Pabon, “A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P4 -sparse graphs,” Inf. Process. Lett., pp. 600–603, 2015. [Online]. Available: http://dx.doi.org/10.1016/j.ipl.2015.02.007
  11. J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices,” Journal of Research of the National Bureau of Standards B, pp. 125–130, 1965. [Online]. Available: http://archive.org/details/jresv69Bn1-2p125
  12. V. V. Lozin and M. Milanic, “A polynomial algorithm to find an independent set of maximum weight in a fork-free graph,” J. Discrete Algorithms, pp. 595–604, 2008. [Online]. Available: http://dx.doi.org/10.1016/j.jda.2008.04.001
  13. J. Edmonds, “Paths, trees, and flowers,” Canad. J. Math., pp. 449–467, 1965. [Online]. Available: http://dx.doi.org/10.4153/CJM-1965-045-4
  14. C. Berge, “Two theorems in graph theory,” Proceedings of the National Academy of Sciences of the United States of America, pp. 842–844, 1957. [Online]. Available: http://www.jstor.org/stable/89875
  15. V. V. Lozin, “Conic reduction of graphs for the stable set problem,” Discrete Mathematics, pp. 199–211, 2000. [Online]. Available: http://dx.doi.org/10.1016/S0012-365X(99)00408-2
  16. A. Brandstädt and P. L. Hammer, “On the stability number of claw-free P5-free and more general graphs,” Discrete Applied Mathematics, pp. 163–167, 1999. [Online]. Available: http://dx.doi.org/10.1016/S0166-218X(99)00072-4
  17. L. Lovàsz and M. D. Plummer, Matching theory. Amsterdam, New York: North-Holland, 1986. [Online]. Available: http://opac.inria.fr/record=b1086098
  18. P. A. Catlin, “A reduction method for graphs,” in Proc. 19th Southeastern Conf. (Baton Rouge), Congressus Numerantium 65, 1988, pp. 159–170.
  19. A. Goldman and Y. Ngoko, “On graph reduction for qos prediction of very large web service compositions,” in IEEE Ninth International Conference on Services Computing, Honolulu, HI, USA, 2012, pp. 258–265. [Online]. Available: http://dx.doi.org/10.1109/SCC.2012.21
  20. J. Cardoso, A. P. Sheth, J. A. Miller, J. Arnold, and K. Kochut, “Quality of service for workflows and web service processes,” J. Web Sem., pp. 281–308, 2004. [Online]. Available: http://dx.doi.org/10.1016/j.websem.2004.03.001
  21. H. N. de Ridder et al., “Information System on Graph Classes and their Inclusions (ISGCI),” http://www.graphclasses.org.