Metric Dimension (graph Theory)
In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.
Read more about Metric Dimension (graph Theory): Detailed Definition, Trees, Properties
Famous quotes containing the word dimension:
“Le Corbusier was the sort of relentlessly rational intellectual that only France loves wholeheartedly, the logician who flies higher and higher in ever-decreasing circles until, with one last, utterly inevitable induction, he disappears up his own fundamental aperture and emerges in the fourth dimension as a needle-thin umber bird.”
—Tom Wolfe (b. 1931)