Radius (Graph Metrics)

From Algorithm Wiki
Jump to navigation Jump to search

Description

Given a graph $G = (V, E)$, determine the radius $r$ of the graph, i.e. the minimum eccentricity over all of the vertices of the graph

Related Problems

Generalizations: Eccentricity

Related: Median, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter, constant sensitivity (4/3)-approximate incremental diameter, 1-sensitive (4/3)-approximate decremental eccentricity

Parameters

$V$: number of vertices

$E$: number of edges

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem Implication Year Citation Reduction
Negative Triangle Detection if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$
then: from-time: $\tilde{O}(T(n,m,M))$
2015 https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 2.3 link