The median of a graph @math is the set of all vertices @math of @math minimizing the sum of distances from @math to all other vertices of @math . It is known that computing the median of dense graphs in subcubic time refutes the APSP conjecture and computing the median of sparse graphs in subquadratic time refutes the HS conjecture. In this paper, we present a linear time algorithm for computing medians of median graphs, improving over the existing quadratic time algorithm. Median graphs constitute the principal class of graphs investigated in metric graph theory, due to their bijections with other discrete and geometric structures (CAT(0) cube complexes, domains of event structures, and solution sets of 2-SAT formulas). Our algorithm is based on the known majority rule characterization of medians in a median graph @math and on a fast computation of parallelism classes of edges ( @math -classes) of @math . The main technical contribution of the paper is a linear time algorithm for computing the @math -classes of a median graph @math using Lexicographic Breadth First Search (LexBFS). Namely, we show that any LexBFS ordering of the vertices of a median graph @math has the following : the fathers of any two adjacent vertices of @math are also adjacent. Using the fast computation of the @math -classes of a median graph @math , we also compute the Wiener index (total distance) of @math in linear time.
Abstract Motivated by a dynamic location problem for graphs, Chung, Graham and Saks introduced a graph parameter called windex. Graphs of windex 2 turned out to be, in graph-theoretic language, retracts of hypercubes. These graphs are also known as median graphs and can be characterized as partial binary Hamming graphs satisfying a convexity condition. In this paper an O(n 3 2 log n) algorithm is presented to recognize these graphs. As a by-product we are also able to isometrically embed median graphs in hypercubes in O ( m log n ) time. From the Publisher: This study in combinatorial group theory introduces the concept of automatic groups. It contains a succinct introduction to the theory of regular languages, a discussion of related topics in combinatorial group theory, and the connections between automatic groups and geometry which motivated the development of this new theory. It is of interest to mathematicians and computer scientists and includes open problems that will dominate the research for years to come. We show how to test whether a graph with n vertices and m edges is a partial cube, and if so how to find a distance-preserving embedding of the graph into a hypercube, in the near-optimal time bound O(n2), improving previous O(nm)-time solutions. In this note, we characterize the graphs (1-skeletons) of some piecewise Euclidean simplicial and cubical complexes having nonpositive curvature in the sense of Gromov's CAT(0) inequality. Each such cell complex K is simply connected and obeys a certain flag condition. It turns out that if, in addition, all maximal cells are either regular Euclidean cubes or right Euclidean triangles glued in a special way, then the underlying graph G(K) is either a median graph or a hereditary modular graph without two forbidden induced subgraphs. We also characterize the simplicial complexes arising from bridged graphs, a class of graphs whose metric enjoys one of the basic properties of CAT(0) spaces. Additionally, we show that the graphs of all these complexes and some more general classes of graphs have geodesic combings and bicombings verifying the 1- or 2-fellow traveler property. 