Positive Betweenness Centrality: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
Line 14: Line 14:
== Parameters ==  
== Parameters ==  


n: number of nodes
$n$: number of nodes


m: number of edges
$m$: number of edges


== Table of Algorithms ==  
== Table of Algorithms ==  

Latest revision as of 08:53, 10 April 2023

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