Diameter (graph theory)

From Wikipedia, the free encyclopedia
(Redirected from Graph diameter)

Template:Short description Template:DMCA Template:DMCA Template:CS1 config

Graphs with diameters 5 and 28 respectively

In graph theory, the diameter of a connected undirected graph is the farthest distance between any two of its vertices. That is, it is the diameter of a set for the set of vertices of the graph, and for the shortest-path distance in the graph. Diameter may be considered either for weighted or for unweighted graphs. Researchers have studied the problem of computing the diameter, both in arbitrary graphs and in special classes of graphs.

The diameter of a disconnected graph may be defined to be infinite, or undefined.

Graphs of low diameter

The degree diameter problem seeks tight relations between the diameter, number of vertices, and degree of a graph. One way of formulating it is to ask for the largest graph with given bounds on its degree and diameter. For any fixed degree, this maximum size is exponential in diameter, with the base of the exponent depending on the degree.[1]Template:R/superscript

The girth of a graph, the length of its shortest cycle, can be at most 2k+1 for a graph of diameter k. The regular graphs for which the girth is exactly 2k+1 are the Moore graphs. Only finitely many Moore graphs exist, but their exact number is unknown. They provide the solutions to the degree diameter problem for their degree and diameter.[2]Template:R/superscript

Small-world networks are a class of graphs with low diameter, modeling the real-world phenomenon of six degrees of separation in social networks.[3]Template:R/superscript

Algorithms

In arbitrary graphs

The diameter of a graph can be computed by using a shortest path algorithm to compute shortest paths between all pairs of vertices, and then taking the maximum of the distances that it computes. For instance, in a graph with positive edge weights, this can be done by repeatedly using Dijkstra's algorithm, once for each possible starting vertex. In a graph with n vertices and m edges, this takes time O(mn+n2log⁡n). Computing all-pairs shortest paths is the fastest known method for computing the diameter of a weighted graph exactly.[4]Template:R/superscript

In an unweighted-graph, Dijkstra's algorithm may be replaced by a breadth-first search, giving time O(mn). Alternatively, the diameter may be computed using an algorithm based on fast matrix multiplication, in time proportional to the time for multiplying n×n matrices, approximately O(n2.37) using known matrix multiplication algorithms.[5]Template:R/superscript For sparse graphs, with few edges, repeated breadth-first search is faster than matrix multiplication. Assuming the strong exponential time hypothesis, repeated breadth-first search is near-optimal: this hypothesis implies that no algorithm can achieve time O(m2−ε) for any ε>0.[4]Template:R/superscript

It is possible to approximate the diameter of a weighted graph to within an approximation ratio of 3/2, in time O~(min⁡(m3/2,mn2/3), where the O~ notation hides logarithmic factors in the time bound.[6]Template:R/superscript Under the strong exponential time hypothesis, no substantially more accurate approximation, substantially faster than all pairs shortest paths, is possible.[4]Template:R/superscript

In special classes of graphs

The diameter can be computed in linear time for interval graphs,[7]Template:R/superscript and in near-linear time for graphs of bounded treewidth.[8]Template:R/superscript In median graphs, the diameter can be found in the subquadratic time bound O~(n1.6456).[9]Template:R/superscript In any class of graphs closed under graph minors, such as the planar graphs, it is possible to compute the diameter in subquadratic time, with an exponent depending on the graph family.[10]Template:R/superscript

See also

References

  1. ^ Page Module:Citation/CS1/styles.css has no content.Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics, Dynamic survey: DS14
  2. ^ Page Module:Citation/CS1/styles.css has no content.Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF), Linear Algebra and Its Applications, 569: 1–14, doi:10.1016/j.laa.2018.12.035, hdl:2117/127212, MR 3901732, S2CID 126689579
  3. ^ Page Module:Citation/CS1/styles.css has no content.Amaral, L. A. N.; Scala, A.; Barthélémy, M.; Stanley, H. E. (September 2000), "Classes of small-world networks", Proceedings of the National Academy of Sciences, 97 (21): 11149–11152, arXiv:cond-mat/0001458, Bibcode:2000PNAS...9711149A, doi:10.1073/pnas.200327197, PMC 17168, PMID 11005838
  4. ^ a b c Page Module:Citation/CS1/styles.css has no content.Roditty, Liam; Vassilevska Williams, Virginia (2013), "Fast approximation algorithms for the diameter and radius of sparse graphs", in Boneh, Dan; Roughgarden, Tim; Feigenbaum, Joan (eds.), Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, Association for Computing Machinery, pp. 515–524, doi:10.1145/2488608.2488673, ISBN 978-1-4503-2029-0
  5. ^ Page Module:Citation/CS1/styles.css has no content.Cygan, Marek; Gabow, Harold N.; Sankowski, Piotr (2012), "Algorithmic applications of Baur-Strassen's theorem: shortest cycles, diameter and matchings", 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, IEEE Computer Society, pp. 531–540, arXiv:1204.1616, doi:10.1109/FOCS.2012.72, ISBN 978-0-7695-4874-6
  6. ^ Page Module:Citation/CS1/styles.css has no content.Chechik, Shiri; Larkin, Daniel H.; Roditty, Liam; Schoenebeck, Grant; Tarjan, Robert Endre; Vassilevska Williams, Virginia (2014), "Better approximation algorithms for the graph diameter", in Chekuri, Chandra (ed.), Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, SIAM, pp. 1041–1052, doi:10.1137/1.9781611973402.78, ISBN 978-1-61197-338-9
  7. ^ Page Module:Citation/CS1/styles.css has no content.Olariu, Stephan (1990), "A simple linear-time algorithm for computing the center of an interval graph", Int. J. Comput. Math., 34 (3–4): 121–128, doi:10.1080/00207169008803870
  8. ^ Page Module:Citation/CS1/styles.css has no content.Bringmann, Karl; Husfeldt, Thore; Magnusson, Måns (2020), "Multivariate analysis of orthogonal range searching and graph distances", Algorithmica, 82 (8): 2292–2315, doi:10.1007/s00453-020-00680-z, MR 4132892
  9. ^ Page Module:Citation/CS1/styles.css has no content.Bergé, Pierre; Ducoffe, Guillaume; Habib, Michel (2024), "Subquadratic-time algorithm for the diameter and all eccentricities on median graphs", Theory of Computing Systems, 68 (1): 144–193, arXiv:2110.02709, doi:10.1007/s00224-023-10153-9, MR 4699679
  10. ^ Page Module:Citation/CS1/styles.css has no content.Ducoffe, Guillaume; Habib, Michel; Viennot, Laurent (2022), "Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension", SIAM Journal on Computing, 51 (5): 1506–1534, arXiv:1907.04385, doi:10.1137/20M136551X, MR 4502132
Retrieved from "http://cosmopedia.co/index.php?title=Diameter_(graph_theory)&oldid=1500964"