Radius (Graph Metrics)
Revision as of 10:28, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Radius (Graph Metrics)}} == 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...")
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.ezproxy.canberra.edu.au/doi/10.1137/1.9781611973730.112, Lemma 2.3 | link |