An Almost Deterministic Algorithm for Finding All Possible Metric Bases for Honeycomb Networks and Enhanced Honeycomb Networks of Dimension Two to Six
摘要
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.