文章基本信息

标题：Medians in Median Graphs and Their Cube Complexes in Linear Time
本地全文：下载
作者：Laurine Bnteau ; Jrmie Chalopin ; Victor Chepoi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：10:1-10:17
DOI：10.4230/LIPIcs.ICALP.2020.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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, improving over the existing quadratic time algorithm. We also present a linear time algorithm to compute medians in the ð"â,-cube complexes associated with median graphs. Median graphs constitute the principal class of graphs investigated in metric graph theory and have a rich geometric and combinatorial structure. 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 or hyperplanes) via Lexicographic Breadth First Search (LexBFS). To prove the correctness of our algorithm, we show that any LexBFS ordering of the vertices of G satisfies the following fellow traveler property of independent interest: the parents of any two adjacent vertices of G are also adjacent.
关键词：Median Graph; CAT(0) Cube Complex; Median Problem; Linear Time Algorithm; LexBFS