Browsing by Author "Perera, K.K.K.R."

Now showing 1 - 4 of 4

Centrality Measures to Identify Traffic Congestion on Road Networks: A Case Study of Sri Lanka.
(IOSR Journal of Mathematics (IOSR-JM), Department of Mathematics, Faculty of Science, University of Kelaniya, Sri Lanka., 2017) Jayaweera, I.M.L.N.; Perera, K.K.K.R.; Munasinghe, J.
This study presents a graph theoretical approach to identify the traffic congestion on a road network. Problem address on a city called Kiribathgoda situated in the western province of Sri Lanka. In the analysis of social networks, centrality measures played a vital role to identify the central nodes in a given network. We look at the applicability of centrality and betweenness measures in order to identify the most important locations which directly affect to the traffic congestion in road networks in Sri Lanka. Using the graph theoretical approach a traffic network for a selected area was constructed and several centrality measures were calculated. According to our simulation results, it was noted that the practically identified locations could be identified from the simulations carried out using the centrality measures.
Edge metric dimension of bicyclic graphs
(University of Colombo, Sri Lanka, 2025) Gayathrika, K.G.E.H.; Perera, K.K.K.R.
Background Slater introduced the ‘metric dimension’(MD) concept in 1975 [4] to provide a framework for uniquely identifying the location of vertices in a connected graph using distances to a specific subset of vertices. In the last decade, this concept has drawn considerable interest from researchers, due to the wide range of applications in computer science, social networks, chemistry, biology, and many others. In 1976, Harary and Melter [5] further investigated the concept and introduced the term ‘resolving set’. The Resolving set is a subset of vertices such that every vertex on the graph can be uniquely identified by its distances to the vertices in this subset, and the MD is the size of the smallest resolving set of that graph. MD has several variants, and ‘edge metric dimension’(EMD) introduced by Kelenc et al. focuses on identifying edges using a minimal resolving set [1]. Notably, this parameter can also be interpreted as the MD of the line graph, where the vertices represent the edges of the original graph and two vertices are connected if they are adjacent in the original graph. EMD is used to design resilient networks and optimize resources in systems. Recently, the EMD of certain families of graphs such as cycles, trees, complete bipartite graphs, trees and circulant graphs has been studied [3]. This study focuses on finding EMD in three types of bicyclic graphs that have not previously been studied. Bicyclic graphs play a vital role in chemical compound analysis, biological networks, and network design etc. Despite significant research on MD, its variant, EMD remained largely unexplored in the context of bicyclic graphs, and the objective here is to fill this research gap. Methods In this paper, graph is represented by G and it’s line graph as L(G). Vertex set v1, v2, ..., vn and edge set e1, e2, ..., en of G is represented by V (G) and E(G) respectively. For simplicity, edge metric dimension of graph G is represented by (dimE (G)). Three types of bicyclic graphs defined in [2] are used in this research. We denote the number of vertices in two cycles by n and m and the length of the path as r. Type I: Cn,m(n, m ≥ 3): Two disjoint cycles sharing a vertex. Type II: Cn,r,m(n, m ≥ 3, r ≥ 1): Two disjoint cycles connected by a path Type III: (θn,n,n(n ≥ 1)): Three pairs of internally disjoint paths, each of length n, were constructed to connect two vertices. Starting from the proper labeling of three types of bicyclic graphs(G) and the corresponding line graphs were constructed (Figures 1 to 4). The EMD is determined analytically and using Python simulations by varying the number of vertices in cycles and paths (n, m, r). Resolving sets (W ) were identified, and vertex sets were partitioned based on their distances to W. A case study demonstrated that all vertices have distinct representations with respect to W, establishing |W| as an upper bound for EMD. Using mathematical proofs, the lower bound was also shown to be equal to |W|, concluding that dimE (G) = |W| for the analyzed graphs. Results and Conclusions The results revealed that all bicyclic graphs have a constant EMD and depend on structural properties, specifically the number of vertices in their cycles and paths. The edge metric dimensions of the type I, II, and III bicyclic graphs are dimE (Cn,m) = 3, dimE (Cn,r,m) = 2, dimE (θn,n,n) = 2, respectively. For a Type I bicyclic graph, the edge metric basis is W = {e1, en, en+m}, for a Type II, W = {e1, en+r+m}, and for a specific case of Type III θ-graphs, W = {e1, en+1}. Having constant EMDs for all bicyclic graphs highlights their efficiency in applications such as resilient network design and molecular modeling. The study contributes to graph theory by addressing a theoretical gap and providing a foundation for exploring metric dimensions in more complex graphs.
Image segmentation based on spectral clustering methods
(Faculty of Science, University of Kelaniya, Sri Lanka, 2016) Rathnayaka, R.M.D.D.; Perera, K.K.K.R.
Image segmentation is a process of partitioning a digital image into smaller parts or small region to highlight the much important parts of an image. Segmented parts of an image should possess similar properties such as intensity, texture, color etc. Spectral clustering methods are based on eigenvectors of Laplacian matrices associated with the graphs. In this study, we considered a digital image as a graph and used various existing clustering methods to find the segmentations. Second smallest eigenvector of generalized eigensystem, the recursive two way normalized cut method, simultaneous k-way cut with multiple eigenvectors and k-means algorithms are used to partition the images. We compare the clusters obtained from these methods and identify the most efficient method in order to classify the images we considered. Calinski – Harabasz measure and gap evaluation criterion are used to evaluate the quality of clusters. Simulations are carried out using Matlab.
Roach type of graphs and the characteristics of their partitioning
(University of Kelaniya, 2013) Perera, K.K.K.R.
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.