Positive Betweenness Centrality (Vertex Centrality)

From Algorithm Wiki
Revision as of 08:53, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Description

Given a graph $G=(V,E)$ and a vertex $v \in V$, determine whether the betweenness centrality of $v$ is positive.

Related Problems

Generalizations: Betweenness Centrality

Subproblem: Directed All-Nodes Positive Betweenness Centrality, Undirected All-Nodes Positive Betweenness Centrality

Related: Eccentricity, All-Nodes Median Parity, Approximate Betweenness Centrality, Undirected All-Nodes Positive Betweenness Centrality, Reach Centrality, Directed All-Nodes Reach Centrality, Undirected All-Nodes Reach Centrality, Approximate Reach Centrality

Parameters

$n$: number of nodes

$m$: number of edges

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem Implication Year Citation Reduction
Diameter 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

Reductions FROM Problem

Problem Implication Year Citation Reduction
Diameter 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
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 4.3 link
CNF-SAT if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$
then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$
2015 https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Theorem 4.3 link