Medians in median graphs and their cube complexes in linear time
From MaRDI portal
Publication:2119403
DOI10.1016/j.jcss.2022.01.001zbMath1483.68250arXiv1907.10398OpenAlexW3043943455MaRDI QIDQ2119403
Jérémie 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)
Full work available at URL: https://arxiv.org/abs/1907.10398
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Graphs with \(G^p\)-connected medians ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ Distance labeling schemes for \(K_4\)-free bridged graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bucolic complexes
- Geodesics in CAT(0) cubical complexes
- Median graphs, parallelism and posets
- Medians in median graphs
- On the maximum number of cliques in a graph
- The algebraic degree of geometric optimization problems
- Petri nets, event structures and domains. I
- Consensus n-trees
- Event structures and trace monoids
- The structure of median graphs
- Median graphs and Helly hypergraphs
- Recognizing median graphs in subquadratic time
- The majority strategy on graphs
- The median procedure on median graphs
- Geometry of the space of phylogenetic trees
- The median procedure for n-trees
- A tight axiomatization of the median procedure on median graphs
- Graphs of some CAT(0) complexes
- Rabin's theorem in the concurrency setting: a conjecture
- Condorcet domains, median graphs and the single-crossing property
- Computing median and antimedian sets in median graphs
- Combinatorics of lopsided sets
- The centrality index of a graph
- Distance-preserving subgraphs of hypercubes
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- Graphs with Connected Medians
- Computing Medians and Means in Hadamard Spaces
- Nice Labeling Problem for Event Structures: A Counterexample
- Metric Ternary Distributive Semi-Lattices
- Weakly Modular Graphs and Nonpositive Curvature
- State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
- n‐cubes and median graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
- On Distance-Preserving and Domination Elimination Orderings
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Stable networks and product graphs
- Ends of Group Pairs and Non-Positively Curved Cube Complexes
- 1-Safe Petri Nets and Special Cube Complexes
- A counterexample to Thiagarajan's conjecture on regular event structures
- Geometric median in nearly linear time
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- The complexity of satisfiability problems
- Graph-Theoretic Concepts in Computer Science
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- A ternary operation in distributive lattices
