Document Open Access Logo

A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters

Author Guillaume Ducoffe

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.12.pdf
  • Filesize: 470 kB
  • 7 pages

Document Identifiers

Author Details

Guillaume Ducoffe

Cite As Get BibTex

Guillaume Ducoffe. A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 12:1-12:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.12

Abstract

A well-known problem for which it is difficult to improve the textbook algorithm is computing the graph diameter. We present two versions of a simple algorithm (one being Monte Carlo and the other deterministic) that for every fixed h and unweighted undirected graph G with n vertices and m edges, either correctly concludes that diam(G) < hn or outputs diam(G), in time O(m+n^{1+o(1)}). The algorithm combines a simple randomized strategy for this problem (Damaschke, IWOCA'16) with a popular framework for computing graph distances that is based on range trees (Cabello and Knauer, Computational Geometry'09). We also prove that under the Strong Exponential Time Hypothesis (SETH), we cannot compute the diameter of a given n-vertex graph in truly subquadratic time, even if the diameter is an Theta(n/log{n}).

Subject Classification

Keywords
  • Graph diameter
  • Orthogonal Range Queries
  • Hardness in P
  • FPT in P

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Abboud, V. Vassilevska Williams, and J. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In SODA, pages 377-391. SIAM, 2016. URL: https://arxiv.org/abs/1506.01799.
  2. J. Bentley and J. Friedman. Data structures for range searching. ACM Computing Surveys (CSUR), 11(4):397-409, 1979. Google Scholar
  3. P. Berman and S. Kasiviswanathan. Faster approximation of distances in graphs. In WADS, pages 541-552. Springer, 2007. Google Scholar
  4. B. Block and M. Milakovic. Computing Diameters in Slim Graphs. Master’s thesis, Chalmers University of Technology, University of Gothenburg, Sweden, 2018. URL: http://publications.lib.chalmers.se/records/fulltext/255208/255208.pdf.
  5. J. A. Bondy and U. S. R. Murty. Graph theory. Grad. Texts in Math., 2008. Google Scholar
  6. M. Borassi, P. Crescenzi, and M. Habib. Into the square: On the complexity of some quadratic-time solvable problems. Electronic Notes in Theoretical Computer Science, 322:51-67, 2016. URL: https://arxiv.org/abs/1407.4972.
  7. K. Bringmann, T. Husfeldt, and M. Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth. In IPEC. LIPIcs, 2018. to appear. URL: https://arxiv.org/abs/1805.07135.
  8. S. Cabello and C. Knauer. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational Geometry, 42(9):815-824, 2009. Google Scholar
  9. T. Chan. Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back. In 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: http://drops.dagstuhl.de/opus/volltexte/2017/7226.
  10. S. Chechik, D. Larkin, L. Roditty, G. Schoenebeck, R. Tarjan, and V. Vassilevska Williams. Better approximation algorithms for the graph diameter. In SODA, pages 1041-1052. SIAM, 2014. Google Scholar
  11. P. Damaschke. Computing Giant Graph Diameters. In IWOCA, pages 373-384. Springer, 2016. Google Scholar
  12. C. Jordan. Sur les assemblages de lignes. J. Reine Angew. Math, 70(185):81, 1869. Google Scholar
  13. A. Meir and J. Moon. Relations between packing and covering numbers of a tree. Pacific Journal of Mathematics, 61(1):225-233, 1975. Google Scholar
  14. L. Monier. Combinatorial solutions of multidimensional divide-and-conquer recurrences. Journal of Algorithms, 1(1):60-74, 1980. Google Scholar
  15. L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515-524. ACM, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact