Algorithms for the metric dimension of a simple graph
subject: Algorithms; BFS; Locating set; Metric basis; Metric dimension; Resolving set; Spanning tree
description: Let G = (V, E) be a connected, simple graph with n vertices and m edges. Let v1, v2 $$\in$$ V, d(v1, v2) is the number of edges in the shortest path from v1 to v2. A vertex v is said to distinguish two vertices x and y if d(v, x) and d(v, y) are different. D(v) as the set of all vertex pairs which are distinguished by v. A subset of V, S is a metric generator of the graph G if every pair of vertices from V is distinguished by some element of S. Trivially, the whole vertex set V is a metric generator of G. A metric generator with minimum cardinality is called a metric basis of the graph G. The cardinality of metric basis is called the metric dimension of G. In this paper, we develop algorithms to find the metric dimension and a metric basis of a simple graph. These algorithms have the worst-case complexity of O(nm). The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd 2021.
creator: Chelladurai X.; Kureethara J.V.
source: Lecture Notes in Networks and Systems, Vol-132, pp. 91-105.
publisher: Springer
date: 2021-01-01
rights: Restricted Access
relation: ISSN: 23673370
format: Online
language: English
type: Book chapter
coverage: Chelladurai X., CHRIST (Deemed to be University), Bangalore, 560029, India; Kureethara J.V., CHRIST (Deemed to be University), Bangalore, 560029, India