License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.12
URN: urn:nbn:de:0030-drops-100383
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10038/
Go to the corresponding OASIcs Volume Portal

Ducoffe, Guillaume

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

pdf-format:
OASIcs-SOSA-2019-12.pdf (0.5 MB)

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}).

BibTeX - Entry

@InProceedings{ducoffe:OASIcs:2018:10038,
  author =	{Guillaume Ducoffe},
  title =	{{A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{12:1--12:7},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{69},
  editor =	{Jeremy T. Fineman and Michael Mitzenmacher},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10038},
  URN =		{urn:nbn:de:0030-drops-100383},
  doi =		{10.4230/OASIcs.SOSA.2019.12},
  annote =	{Keywords: Graph diameter, Orthogonal Range Queries, Hardness in P, FPT in P}
}

Keywords: Graph diameter, Orthogonal Range Queries, Hardness in P, FPT in P
Collection: 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI