Geodesic
Leanness Computation: Small Values and Special Graph Classes
Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 2.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.12544
Classification : 05C10, 05C82, 05C85 
@article{DMTCS_2024_26_2_a8,
     author = {Coudert, David and Coulomb, Samuel and Ducoffe, Guillaume},
     title = {Leanness {Computation:} {Small} {Values} and {Special} {Graph} {Classes}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2024},
     doi = {10.46298/dmtcs.12544},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12544/}
}
TY  - JOUR
AU  - Coudert, David
AU  - Coulomb, Samuel
AU  - Ducoffe, Guillaume
TI  - Leanness Computation: Small Values and Special Graph Classes
JO  - Discrete mathematics & theoretical computer science
PY  - 2024
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12544/
DO  - 10.46298/dmtcs.12544
LA  - en
ID  - DMTCS_2024_26_2_a8
ER  - 
%0 Journal Article
%A Coudert, David
%A Coulomb, Samuel
%A Ducoffe, Guillaume
%T Leanness Computation: Small Values and Special Graph Classes
%J Discrete mathematics & theoretical computer science
%D 2024
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12544/
%R 10.46298/dmtcs.12544
%G en
%F DMTCS_2024_26_2_a8
Coudert, David; Coulomb, Samuel; Ducoffe, Guillaume. Leanness Computation: Small Values and Special Graph Classes. Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 2. doi : 10.46298/dmtcs.12544. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.12544/

Cité par Sources :