Graph Diameter Measure
Jump to navigation
Jump to search
A Graph Diameter Measure is a graph measure of a maximum graph eccentricity of any graph node in the graph.
- See: Diameter, Graph Distance, Graph Radius.
References
2010
- http://en.wikipedia.org/wiki/Graph_diameter
- … The diameter of a graph is the maximum eccentricity of any vertex in the graph. That is, it is the greatest distance between any pair of vertices. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.
2012
- (Merrill et al., 2012) ⇒ Duane Merrill, Michael Garland, and Andrew Grimshaw. (2012). “Scalable GPU Graph Traversal.” In: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming. ISBN:978-1-4503-1160-1 doi:10.1145/2370036.2145832
- QUOTE: Breadth-first search (BFS) is a core primitive for graph traversal and a basis for many higher-level graph analysis algorithms. … Recent work has demonstrated the plausibility of GPU sparse graph traversal, but has tended to focus on asymptotically inefficient algorithms that perform poorly on graphs with non-trivial diameter.
2009
- http://mathworld.wolfram.com/GraphDiameter.html
- QUOTE: The length max_(u,v)d(u,v) of the "longest shortest path" (i.e., the longest graph geodesic) between any two graph vertices (u,v) of a graph, where d(u,v) is a graph distance. In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration. The above random graphs on 10 vertices have diameters 3, 4, 5, and 7, respectively.
The diameter of a graph may be computed using Diameter[g] in the Mathematica package Combinatorica`, and a fast approximation to the diameter by PseudoDiameter[g] in the Mathematica package GraphUtilities` . Precomputed diameters for many named graphs can be obtained using GraphData[graph, "Diameter"].
- QUOTE: The length max_(u,v)d(u,v) of the "longest shortest path" (i.e., the longest graph geodesic) between any two graph vertices (u,v) of a graph, where d(u,v) is a graph distance. In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration. The above random graphs on 10 vertices have diameters 3, 4, 5, and 7, respectively.