Parallel Algorithm to find Integer k where a given Well-Distributed Graph is k-Metric Dimensional
subject: Metric basis of a graph; Metric dimension; Parallel algorithm for metric dimension; Resolving set
description: Networks are very important in the world. In signal processing, the towers are modeled as nodes (vertices) and if two towers communicate, then they have an arc (edge) between them or precisely, they are adjacent. The least number of nodes in a network that can uniquely locate every node in the network is known in the network theory as the resolving set of a network. One of the properties that is used in determining the resolving set is the distance between the nodes. Two nodes are at a distance one if there is a single arc can link them whereas the distance between any two random nodes in the network is the least number of distinct arcs that can link them. We propose two algorithms in this paper with the proofs of correctness. The first one is in lines with the BFS that find distance between a designated node to every other node in the network. This algorithm runs in O(log n). The second algorithm is to identify the integer k, such that the given graph is k-metric dimensional. This can be implemented in O(log n) time with O(n2) processors in a CRCW PRAM. 2021, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
creator: Chelladurai X.; Kureethara J.V.
source: Advances in Intelligent Systems and Computing, Vol-1333 AISC, pp. 145-153.
publisher: Springer Science and Business Media Deutschland GmbH
date: 2021-01-01
rights: Restricted Access
relation: ISSN: 21945357; ISBN: 978-981336965-8
format: Online
language: English
type: Conference paper
coverage: Chelladurai X., Department of Sciences and Humanities, Christ University, Bangalore, India; Kureethara J.V., Department of Mathematics, Christ University, Bangalore, India