Algorithms for the metric dimension of a simple graph

Title

Algorithms for the metric dimension of a simple graph

Creator

Chelladurai X.; Kureethara J.V.

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.

Source

Lecture Notes in Networks and Systems, Vol-132, pp. 91-105.

Date

2021-01-01

Publisher

Springer

Subject

Algorithms; BFS; Locating set; Metric basis; Metric dimension; Resolving set; Spanning tree

Coverage

Chelladurai X., CHRIST (Deemed to be University), Bangalore, 560029, India; Kureethara J.V., CHRIST (Deemed to be University), Bangalore, 560029, India

Rights

Restricted Access

Relation

ISSN: 23673370

Format

Online

Language

English

Type

Book chapter

Identifier

https://doi.org/10.1007/978-981-15-5309-7_10

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85090370380&doi=10.1007%2f978-981-15-5309-7_10&partnerID=40&md5=bb6607b970fa6b5c25368b687128ee53