Subquadratic-time algorithm for the diameter and all eccentricities on median graphs

DOI10.1007/s00224-023-10153-9arXiv2110.02709OpenAlexW4389309511MaRDI QIDQ6151151

Unnamed Author, Pierre Bergé, Guillaume Ducoffe

Publication date: 9 February 2024

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

diameterhypercubesmedian graphseccentricities

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Approximation algorithms (68W25) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizing almost-median graphs. II.
• Finding and counting given length cycles
• Median graphs, parallelism and posets
• Isometric embedding in products of complete graphs
• Characterizing almost-median graphs
• On the use of ordered sets in problems of comparison and consensus of classifications
• The structure of median graphs
• Median graphs and Helly hypergraphs
• Recognizing median graphs in subquadratic time
• The median procedure on median graphs
• An Euler-type formula for median graphs
• Graphs of some CAT(0) complexes
• Medians in median graphs and their cube complexes in linear time
• Combinatorics of lopsided sets
• Partial Cubes and Crossing Graphs
• Combinatorics and Geometry of Finite and Infinite Squaregraphs
• Metric Ternary Distributive Semi-Lattices
• Retracts of hypercubes
• Three Partition Refinement Algorithms
• Median Graphs and Triangle-Free Graphs
• 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
• Embedding Topological Median Algebras in Products of Dendrons
• Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Better Approximation Algorithms for the Graph Diameter
• Fast approximation algorithms for the diameter and radius of sparse graphs
• A ternary operation in distributive lattices
• Isometric embeddings in trees and their use in distance problems

This page was built for publication: Subquadratic-time algorithm for the diameter and all eccentricities on median graphs