Paper Info
Title
Computing a metric basis of a bipartite distance-hereditary graph
Abstract
A vertex x of a connected graph G resolves two distinct vertices u and v in V (G) if the distance between u and x differs from the distance between v and x. A subset X of V (G) resolves two distinct vertices u and v in G if there exists a vertex x in X that resolves u and v; X is a metric generator of G if, for every pair of distinct vertices u and v of G, X resolves u and v and is a metric basis of G if X is a metric generator of G with minimum cardinality. The metric dimension of G is the cardinality of a metric basis of G. The problem of finding the metric dimension of an arbitrary graph is NP-hard. In this paper we show that the problem is solvable in linear time for the class of bipartite distance-hereditary graphs. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.tcs.2021.11.015
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Metric generator, Metric basis, Bipartite graph, Distance-hereditary graph
Journal
900
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Marina Moscarini100.68