Median: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
V: number of vertices | $V$: number of vertices | ||
E: number of edges | $E$: number of edges | ||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 07:53, 10 April 2023
Description
Given a graph $G = (V, E)$, determine the median $m$ of the graph, where $m := \min\limits_{v\in V} \sum\limits_{u\in V} d(u, v)$
Related Problems
Related: Radius, 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))$ for $n$-node $m$-edge graph with integer weights in $(-M, M)$ then: from-time: $\tilde{O}T(n,M))$ |
2015 | https://epubs-siam-org.ezproxy.canberra.edu.au/doi/10.1137/1.9781611973730.112, Lemma 2.4 | link |