In the Euclidean plane, trilateration is the basic technique for GPS to pinpoint Earth’s surface. However, this task of pinpointing each node in discrete spaces  is  more complex and is generally considered an NP hard problem. The goal is to select a small set of vertices capable of identifying every vertex uniquely based on shortest path distances. Metric dimension of a graph is the smallest number of vertices from which the vector of distances to every vertex in the graph is unique. Finding metric dimension of a graph is one such computational complex problem (in general, NP complete problem). We introduce an almost deterministic algorithm called BIGS (Bharati-Indra-George-Simon) algorithm, which extracts all the metric bases of a graph and we define its total number as BIGS number or BIGS index. In this paper, we found BIGS index of Honeycomb networks and Enhanced Honeycomb networks of dimension two to six by analyzing distance matrices of it using advanced software like MATLAB and JAVA.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Almost Deterministic Algorithm for Finding All Possible Metric Bases for Honeycomb Networks and Enhanced Honeycomb Networks of Dimension Two to Six

  • M. V. Abigail,
  • F. Simon Raj

摘要

In the Euclidean plane, trilateration is the basic technique for GPS to pinpoint Earth’s surface. However, this task of pinpointing each node in discrete spaces  is  more complex and is generally considered an NP hard problem. The goal is to select a small set of vertices capable of identifying every vertex uniquely based on shortest path distances. Metric dimension of a graph is the smallest number of vertices from which the vector of distances to every vertex in the graph is unique. Finding metric dimension of a graph is one such computational complex problem (in general, NP complete problem). We introduce an almost deterministic algorithm called BIGS (Bharati-Indra-George-Simon) algorithm, which extracts all the metric bases of a graph and we define its total number as BIGS number or BIGS index. In this paper, we found BIGS index of Honeycomb networks and Enhanced Honeycomb networks of dimension two to six by analyzing distance matrices of it using advanced software like MATLAB and JAVA.