Displaying similar documents to “Computing Strong Metric Dimension of some Special Classes of Graphs by Genetic Algorithms”

Closed Formulae for the Strong Metric Dimension of Lexicographi

Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Given a connected graph G, a vertex w ∈ V (G) strongly resolves two vertices u, v ∈ V (G) if there exists some shortest u − w path containing v or some shortest v − w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several relationships between the strong metric...

Computing the Metric Dimension of a Graph from Primary Subgraphs

Dorota Kuziak, Juan A. Rodríguez-Velázquez, Ismael G. Yero (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph. Given an ordered set W = {w1, . . . , wk} ⊆ V (G) and a vertex u ∈ V (G), the representation of u with respect to W is the ordered k-tuple (d(u, w1), d(u, w2), . . . , d(u, wk)), where d(u, wi) denotes the distance between u and wi. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum cardinality metric generator is called a metric basis of G and its cardinality is called the metric dimension of...

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2004)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very...

On the strong metric dimension of the strong products of graphs

Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez (2015)

Open Mathematics

Similarity:

Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this...

The local metric dimension of a graph

Futaba Okamoto, Bryan Phinezy, Ping Zhang (2010)

Mathematica Bohemica

Similarity:

For an ordered set W = { w 1 , w 2 , ... , w k } of k distinct vertices in a nontrivial connected graph G , the metric code of a vertex v of G with respect to W is the k -vector code ( v ) = ( d ( v , w 1 ) , d ( v , w 2 ) , ⋯ , d ( v , w k ) ) where d ( v , w i ) is the distance between v and w i for 1 ≤ i ≤ k . The set W is a local metric set of G if code ( u ) ≠ code ( v ) for every pair u , v of adjacent vertices of G . The minimum positive integer k for which G has a local metric k -set is the local metric dimension lmd ( G ) of G . A local metric set of G of cardinality lmd ( G ) is a local metric basis of G . We characterize all nontrivial...