License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.44
URN: urn:nbn:de:0030-drops-144841
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14484/
Go to the corresponding LIPIcs Volume Portal

Ducoffe, Guillaume

On Computing the Average Distance for Some Chordal-Like Graphs

pdf-format:
LIPIcs-MFCS-2021-44.pdf (0.8 MB)

Abstract

The Wiener index of a graph G is the sum of all its distances. Up to renormalization, it is also the average distance in G. The problem of computing this parameter has different applications in chemistry and networks. We here study when it can be done in truly subquadratic time (in the size n+m of the input) on n-vertex m-edge graphs. Our main result is a complete answer to this question, assuming the Strong Exponential-Time Hypothesis (SETH), for all the hereditary subclasses of chordal graphs. Interestingly, the exact same result also holds for the diameter problem. The case of non-hereditary chordal subclasses happens to be more challenging. For the chordal Helly graphs we propose an intricate Õ(m^{3/2})-time algorithm for computing the Wiener index, where m denotes the number of edges. We complete our results with the first known linear-time algorithm for this problem on the dually chordal graphs. The former algorithm also computes the median set.

BibTeX - Entry

@InProceedings{ducoffe:LIPIcs.MFCS.2021.44,
  author =	{Ducoffe, Guillaume},
  title =	{{On Computing the Average Distance for Some Chordal-Like Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{44:1--44:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14484},
  URN =		{urn:nbn:de:0030-drops-144841},
  doi =		{10.4230/LIPIcs.MFCS.2021.44},
  annote =	{Keywords: Wiener index, Graph diameter, Hardness in P, Chordal graphs, Helly graphs}
}

Keywords: Wiener index, Graph diameter, Hardness in P, Chordal graphs, Helly graphs
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

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