1. Medians in median graphs and their cube complexes in linear time.
- Author
-
Bénéteau, Laurine, Chalopin, Jérémie, Chepoi, Victor, and Vaxès, Yann
- Subjects
- *
CUBES , *CHARTS, diagrams, etc. , *TIME , *ALGORITHMS - Abstract
The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs. We also present a linear time algorithm to compute medians in the associated ℓ 1 -cube complexes. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes) via Lexicographic Breadth First Search (LexBFS). We show that any LexBFS ordering of the vertices of a median graph satisfies the following fellow traveler property : the parents of any two adjacent vertices are also adjacent. Using the fast computation of the Θ-classes, we also compute the Wiener index (total distance) in linear time and the distance matrix in optimal quadratic time. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF