Details

Autor(en) / Beteiligte

• Bergé, Pierre
• Habib, Michel

Titel

Diameter in linear time for constant-dimension median graphs

Ist Teil von

• Procedia computer science, 2021, Vol.195, p.97-107

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2021

Link zum Volltext

Quelle

EZB Electronic Journals Library

Beschreibungen/Notizen

• Median graphs form the class of graphs which is the most studied in metric graph theory. Recently, Bénéteau et al. [2019] designed a linear-time algorithm computing both the Θ-classes and the median set of median graphs. A natural question emerges: is there a linear-time algorithm computing the diameter for median graphs? We answer positively to this question for median graphs G with constant dimension d, i.e. the dimension of the largest induced hypercube of G. We propose a combinatorial algorithm computing the diameter of median graphs with running time O(2O(dlogd)n). In particular, since the hypercube Q4 of dimension 4 is not planar, it shows also that the diameter of planar median graphs can be computed in O(n).