Medians in median graphs and their cube complexes in linear time

DOI10.1016/J.JCSS.2022.01.001zbMATH Open1483.68250arXiv1907.10398OpenAlexW3043943455MaRDI QIDQ2119403FDOQ2119403

J. Chalopin, Yann Vaxès, Victor Chepoi, Laurine Bénéteau

Publication date: 29 March 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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, improving over the existing quadratic time algorithm. We also present a linear time algorithm to compute medians in the $el{l}_1$-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, due to their bijections with CAT(0) cube complexes and domains of event structures. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges ($Theta$-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. Using the fast computation of the $Theta$-classes, we also compute the Wiener index (total distance) of $G$ in linear time and the distance matrix in optimal quadratic time.

Full work available at URL: https://arxiv.org/abs/1907.10398

zbMATH Keywords

event structuresmedian graphlinear-time algorithmCAT(0) cube complexmedian problemLexBFS

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometry of the space of phylogenetic trees
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
• Petri nets, event structures and domains. I
• Consensus n-trees
• Graphs of some CAT(0) complexes
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• The complexity of satisfiability problems
• n‐cubes and median graphs
• Distance-preserving subgraphs of hypercubes
• Computing Medians and Means in Hadamard Spaces
• Algorithmic Aspects of Vertex Elimination on Graphs
• The median procedure on median graphs
• A tight axiomatization of the median procedure on median graphs
• The algebraic degree of geometric optimization problems
• The centrality index of a graph
• Metric Ternary Distributive Semi-Lattices
• On the maximum number of cliques in a graph
• Ends of Group Pairs and Non-Positively Curved Cube Complexes
• Graph-Theoretic Concepts in Computer Science
• Bucolic complexes
• Combinatorics of lopsided sets
• The median procedure for n-trees
• On Distance-Preserving and Domination Elimination Orderings
• A ternary operation in distributive lattices
• Geodesics in CAT(0) cubical complexes
• Medians in median graphs
• Event structures and trace monoids
• Median graphs and Helly hypergraphs
• Nice Labeling Problem for Event Structures: A Counterexample
• Stable networks and product graphs
• Median graphs, parallelism and posets
• Computing median and antimedian sets in median graphs
• The structure of median graphs
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Recognizing median graphs in subquadratic time
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Graphs with connected medians
• The majority strategy on graphs
• Weakly Modular Graphs and Nonpositive Curvature
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Rabin's theorem in the concurrency setting: a conjecture
• Geometric median in nearly linear time
• Condorcet domains, median graphs and the single-crossing property
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• 1-Safe Petri Nets and Special Cube Complexes
• A counterexample to Thiagarajan's conjecture on regular event structures

Cited In (12)

• Fibonacci \((p,r)\)-cubes which are median graphs
• An axiomatization of the median procedure on the \(n\)-cube
• Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
• A fixed cube theorem for median graphs
• Boundary rigidity of CAT(0) cube complexes
• Computing the blocks of a quasi-median graph
• Distance problems within Helly graphs and \(k\)-Helly graphs
• Recognizing median graphs in subquadratic time
• On cube-free median graphs
• Graphs with \(G^p\)-connected medians
• Title not available (Why is that?)
• Distance labeling schemes for \(K_4\)-free bridged graphs

This page was built for publication: Medians in median graphs and their cube complexes in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2119403)