Leanness Computation: Small Values and Special Graph Classes
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 unde...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-07-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/12544/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1365-8050 |