In our Research Journey, an algorithm and software coding were revealed to me. It is useful to find all metric bases of a given graph in a reasonable time. For some graphs , we get all metric bases in a fraction of a second, but for graphs with 2^7 nodes, we get the first answer in 5 minutes and complete answers ( 73728 bases) for Q(6,3 ) in 12 minutes , and More than 1Lakh metric bases for Q(7,3) with running time, 4 hours, 54 minutes and 30 seconds,( Is It reasonable time?). I would like to know about the existing algorithm (if exist) to find all metric bases of a given graph. It is also interesting to see that the metric dimension of Enhanced Hypercube Q(n,3) is a constant , for n= 3 to 7).
Perhaps you may check an algorithm for determine metric dimension on graphs given in this article:
https://iopscience.iop.org/article/10.1088/1742-6596/1494/1/012018/pdf
Thank you for your reply. I am looking for algorithms as well as Sofware coding and Literature Survey on this topics. Thank you.
Hi Simon! Finding the metric dimension is NP-hard, so any known algorithms will be impracticable for even relatively small graphs. So the best that one can hope for is an efficient algorithm for approximating the metric dimension.
Two papers that give methods for doing this are 'Computing the metric dimension of graphs by genetic algorithms' by Kratica, Kovacevic-Vujcic & Cangalovic (with some missing accents!) and 'Variable neighborhood search for metric dimension and minimal doubly resolving set problems' by Mladenovic, Kratica, Kovacevic-Vujcic & Cangalovic. However, there is no guarantee that the resolving sets produced by these algorithms will be close to the real answer.
However the article 'Approximation complexity of metric dimension problem' by Hauptmann, Schmied & Viehmann gives an algorithm that is guaranteed to be out by at most a logarithmic factor. In this sense the metric dimension seems to be easier to approximate than the chromatic number or general position number, for example.
Thank You James for you contribution. Kindly give one graph for which finding metric dimension very difficult in reasonable time, our team will give metric dimension of that graph with in 1 second to 5 hours (Maximum 2^7 nodes). Kindly contact me for sharing your graph ( watsup Indian number ) +919444045417. Or Mail id [email protected]. We will give exact answer and all possible metric bases of given graph.
Time complexity =O(2^n), but we got all the Metric base of Enhanced hypercube Q(n,2) (for n= 4 to 6) less than one minute time duration and for Q(7, 2), 12 minutes. For Q(n,3) (for n= 3 to 7) running time is from one second to 4 hours and 55 minutes. We got the first metric basis output from 1 second to 45 minutes. Verified for graph with 8 nodes to 128 Nodes. We will prove that the Problem of finding Metric dimension of any graph is in P-Class very soon, How ever finding the conditional resolving set problems is still in NP class.
- Badges
- Science topic
- Similar topics
- Filing