David Coudert ; Samuel Coulomb ; Guillaume Ducoffe - Leanness Computation: Small Values and Special Graph Classes

dmtcs:12544 - Discrete Mathematics & Theoretical Computer Science, July 8, 2024, vol. 26:2 - https://doi.org/10.46298/dmtcs.12544
Leanness Computation: Small Values and Special Graph ClassesArticle

Authors: David Coudert ORCID1; Samuel Coulomb 2; Guillaume Ducoffe 3,4

Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as "interval thinness" and "fellow traveler property". Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., COMPLEX NETWORKS'21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.


Volume: vol. 26:2
Section: Graph Theory
Published on: July 8, 2024
Accepted on: June 3, 2024
Submitted on: November 13, 2023
Keywords: Leanness,Geodetic graphs,SETH-based lower bounds,Graph algorithms,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Funding:
    Source : HAL
  • Idex UCA JEDI; Funder: French National Research Agency (ANR); Code: ANR-15-IDEX-0001

Consultation statistics

This page has been seen 74 times.
This article's PDF has been downloaded 20 times.