Diameter: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Diameter (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, determine the diameter $d$ of the graph, i.e. the maximum eccentricity over all of the vertices of the graph == Related Problems == Generalizations: Eccentricity Subproblem: Approximate Diameter, Decremental Diameter Related: Median, Radius, Diameter 2 vs 3, Diameter 3 vs 7, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diame...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 14: | Line 14: | ||
== Parameters == | == Parameters == | ||
$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 diameter $d$ of the graph, i.e. the maximum eccentricity over all of the vertices of the graph
Related Problems
Generalizations: Eccentricity
Subproblem: Approximate Diameter, Decremental Diameter
Related: Median, Radius, Diameter 2 vs 3, Diameter 3 vs 7, 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 TO Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Reach Centrality | if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 3.1 | link |
| Positive Betweenness Centrality | if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 4.1 | link |
| Approximate Betweenness Centrality | 2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Theorem 4.2 | link |
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Reach Centrality | 2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, | link | |
| Reach Centrality | if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed graph with integer weights in $(-M,M)$ then: from-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed graph with integer weights in $(-M,M)$ |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 3.2 | link |
| Positive Betweenness Centrality | if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed (resp. undirected) graph with integer weights in $(-M,M)$ then: from-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed (resp. undirected) graph with integer weights in $(-M,M)$ |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 4.2 | link |
| Approximate Betweenness Centrality | 2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Theorem 4.2 | link | |
| Betweenness Centrality (BC) | if: to-time: Truly subcubic then: from-time: Truly subcubic Monte-Carlo PTAS |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 4.10 | link |