- Title
- Metric dimension of directed graphs
- Creator
- Rajan, Bharati; Rajasingh, Indra; Cynthia, Jude Annie; Manuel, Paul
- Relation
- International Journal of Computer Mathematics Vol. 91, Issue 7, p. 1397-1406
- Publisher Link
- http://dx.doi.org/10.1080/00207160.2013.844335
- Publisher
- Taylor & Francis
- Resource Type
- journal article
- Date
- 2014
- Description
- A metric basis for a digraph G(V, A) is a set W⊂V such that for each pair of vertices u and v of V, there is a vertex w∈W such that the length of a shortest directed path from w to u is different from the length of a shortest directed path from w to v in G; that is d(w, u)≠d(w, v). A minimum metric basis is a metric basis of minimum cardinality. The cardinality of a minimum metric basis of G is called the metric dimension and is denoted by β (G). In this paper, we prove that the metric dimension problem is NP-complete for directed graphs by a reduction from 3-SAT. The technique adopted is due to Khuller et al. [Landmarks in graphs, Discrete Appl. Math. 70(3) (1996), pp. 217–229]. We also solve the metric dimension problem for De Bruijn and Kautz graphs in polynomial time.
- Subject
- metric basis; metric dimension; directed graph; NP-completeness; 3-SAT
- Identifier
- http://hdl.handle.net/1959.13/1301981
- Identifier
- uon:20385
- Identifier
- ISSN:0020-7160
- Language
- eng
- Reviewed
- Hits: 2226
- Visitors: 2190
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|