Social Network Analysis and Mining Прикладные компьютерные науки

On computing Banzhaf power index for k-edge connectivity in graphs

Narayanam, Lakshmi Satya Vani, Motammanavar, Satish V.
Springer Nature · 2022-10-29 · DOI 10.1007/s13278-022-00985-7

Аннотация

Consider an undirected and unweighted graph $$G=(V,E)$$ G = ( V , E ) where V is the set of vertices and E is the set of edges. Let P be a set of pairs of vertices in G . For a given integer k , we assume that there exists at least k edge disjoint paths between pairs of vertices in P . We consider a new problem that studies the role played by each edge in G to maintain at least k edge disjoint paths between pairs of vertices in P . Hereafter, we refer to this as pairwise k-edge connectivity problem. We compute the Banzhaf power index of each edge to tackle pairwise k -edge connectivity problem that determines the value that edge plays in establishing at least k edge disjoint paths between vertex pairs in P . In particular, we show that computing the Banzhaf power indices of the edges for pairwise k -edge connectivity is $$\#P$$ # P -complete. We also derive a closed form expression for the Banzhaf power index in the k -edge connectivity problem when the graph is a tree.

Читать у издателя →