Directed All-Nodes Positive Betweenness Centrality (Vertex Centrality)

From Algorithm Wiki
Revision as of 07: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 directed graph, determine whether the betweenness centrality of all nodes is positive.

Related Problems

Generalizations: Positive Betweenness Centrality

Related: Eccentricity, All-Nodes Median Parity, Betweenness Centrality, 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 FROM Problem

Problem Implication Year Citation Reduction
Directed, Weighted APSP if: to-time: Truly subcubic
then: from-time: Truly subcubic		 2015 https://epubs-siam-org.ezproxy.canberra.edu.au/doi/10.1137/1.9781611973730.112, Corollary 4.1 link
Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Directed_All-Nodes_Positive_Betweenness_Centrality&oldid=46908"