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.
As noticed above, the @math -classes of a median graph @math correspond to coordinates of the hypercube in which @math isometrically embeds. Thus one can define @math -classes for all partial cubes. Eppstein @cite_29 performed an efficient computation of @math -classes as a main step of his @math algorithm for recognizing partial cubes. For this, he runs several Breadth First Searches (BFS) on the input graph. The computation of @math -classes of a median graph in @math time by , @cite_22 was used in their subquadratic recognition of median graphs. The fellow-traveler property (which is essential in our computation of @math -classes) is a notion coming from geometric group theory @cite_9 and is one of the principal tool used to prove the biautomaticity of a group. In a slightly stronger form it allows to establish dismantlability of graphs (see, for example, @cite_49 @cite_3 and references therein for classes of graphs in which such fellow traveler order can be obtained by BFS or LexBFS).
@cite_22 @cite_9 @cite_29 @cite_3 @cite_49
1994784589 2073943982 2092349993 2094731111
A median of a family of vertices in a graph is any vertex whose distance-sum to that family is minimum. In the framework of metric spaces the problem of minimizing a distance-sum is often referred to as the Fermat problem. On the other hand, medians have been studied from a purely order-theoretic or combinatorial point of view (for instance, in statistics, or in Jordan’s work [12] on trees). The aim of this paper is to investigate the mutual relationship of the metric and the ordinal combinatorial approaches to the median problem in the class of median graphs. A connected graph is a median graph if any three vertices admit a unique median (see Avann [l]). Note that trees and the covering graphs of distributive lattices are median graphs. Very little is known about medians in arbitrary graphs (cf. Slater [20]); so far, only trees (Zelinka [22], and many others) and the covering graphs of distributive lattices (Barbut [4]) have been considered. In both cases we get that (i) the medians of any family form an interval (a path in a tree, an order-theoretic interval in a distributive lattice), and (ii) medians of odd numbered families are unique (see Slater [19] for trees, and Barbut [4] for distributive lattices). These results point to the fact that (i) and (ii) must be true for any median graph. After recalling some basic definitions and facts concerning median graphs and median semilattices (for further information, see Bandelt and Hedlikova [3]), we establish (i) and (ii) for arbitrary median graphs. Our results are based on theorems of Avann, Sholander, and Barbut. In trees medians have nice local properties (cf. [7]). Indeed, median sets are related to mass centers (Zelinka [22]) and security centers (Slater [18]). In Section 3 this is extended to median graphs. The study of medians applies to social choice theory (see Barbut 151, and Barthelemy and Monjardet [8]). The median procedure is strongly related to the simple majority rule: the median of a family (A,, . . . , Azk+ ,) of subsets of a set X may be written as U n Ai (Barbut’s formula). 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. Chapter 36 Decomposing Graphs into Regions of Small Diameter* Nathan Linialt Michael .lss A decomposition of a graph G = (V, E) is a partition of the vertex set into subsets (called lhks). The diameter of a decomposition is the least. d such that any two vertices belonging to the same connected component of a block are at distance < d. In this paper we prove (nearly best possible) statements of the form: .4ny n–vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [AGLP1 it was shown that every graph has a decomposition into at most s(n) blocks of diameter at most s(n) for s(n) = o( loglog d h n). usinga,technique of Awerbuch [A] and Awerbuch and Peleg [AP], we improve this result by showing that every graph has a decomposition of diameter ()(log n) into O(log n) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in time 0(log2 n). The construction can be parametrized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible for two families of graphs the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner’s lemma for the first class and Tucker’s lemma for the second. *This work was supported in part by NSF contracts DMS87-03541 and CCR-8911388 tDepartment of Computer Science, Hebrew University, Jerusalem, Israel. + ‘Department of Computer Science and Engineering, Mail Code C-014, University of California, San Diego, La Jolla, CA 92093-0114. 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.