Parallel Algorithm to find Integer k where a given Well-Distributed Graph is k-Metric Dimensional

Title

Parallel Algorithm to find Integer k where a given Well-Distributed Graph is k-Metric Dimensional

Creator

Chelladurai X.; Kureethara J.V.

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.

Source

Advances in Intelligent Systems and Computing, Vol-1333 AISC, pp. 145-153.

Date

2021-01-01

Publisher

Springer Science and Business Media Deutschland GmbH

Subject

Metric basis of a graph; Metric dimension; Parallel algorithm for metric dimension; Resolving set

Coverage

Chelladurai X., Department of Sciences and Humanities, Christ University, Bangalore, India; Kureethara J.V., Department of Mathematics, Christ University, Bangalore, India

Rights

Restricted Access

Relation

ISSN: 21945357; ISBN: 978-981336965-8

Format

Online

Language

English

Type

Conference paper

Identifier

https://doi.org/10.1007/978-981-33-6966-5_15

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85104776016&doi=10.1007%2f978-981-33-6966-5_15&partnerID=40&md5=0b138839b133c716a59119e3f63b5318