Digital Repository

Roach type of graphs and the characteristics of their partitioning

Show simple item record

dc.contributor.author Perera, K.K.K.R.
dc.date.accessioned 2015-06-26T06:29:28Z
dc.date.available 2015-06-26T06:29:28Z
dc.date.issued 2013
dc.identifier.citation Perera, K.K.K.R., 2013. Roach type of graphs and the characteristics of their partitioning, Proceedings of the Annual Research Symposium 2013, Faculty of Graduate Studies, University of Kelaniya, pp 97. en_US
dc.identifier.uri
dc.identifier.uri http://repository.kln.ac.lk/handle/123456789/8593
dc.description.abstract The goal of the graph partitioning problem is to find groups such that entities within the same group are similar and different groups are dissimilar. Spectral clustering methods use eigenvalues and eigenvectors of matrices associated with graphs and are widely used in graph-partitioning problems. In this presentation, results concerning spectral clustering properties of roach type of graphs ( and are the number of vertices in the upper and lower paths of the graph) will be presented. The concrete formula for the minimum normalized cut of has already been presented, (Perera & Mizoguchi, 2013). The normalized cut is used to minimize the disassociation between partitions of graphs and maximize the association within partitions. Here we find the characteristic polynomials for the normalized Laplacian matrix of weighted path and roach type of graphs using Chebyshev polynomials and properties of tridiagonal matrices. Subsequently, we find conditions for and , based on which spectral methods perform poorly compared with the minimum normalized cut. en_US
dc.language.iso en en_US
dc.publisher University of Kelaniya en_US
dc.title Roach type of graphs and the characteristics of their partitioning en_US
dc.type Article en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account