Satish Motammanavar

Consider an undirected and unweighted graph 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-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. � 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Austria, part of Springer Nature.

This paper presents two new problems in the context of signed social networks and then conducts a systematic analysis of the same. These problems essentially deal with finding groups of specific cardinality that satisfy certain stability requirements. In particular, we define two notions of stability in signed social networks, namely internal stability and external stability. We call a group internally stable if the difference between positive edges and negative edges within the group is maximum. A group for which the difference between positive incoming edges and negative incoming edges from outside the group, is maximum, is externally stable. Based on these notions of internal and external stability, we define two important problems: The comprehensively stable group problem and the internally stable group problem. Given an integer k, the comprehensively stable group problem deals with finding a group of k nodes that satisfies both internal stability and external stability. This problem is applicable in the context of finding trustworthy well-functioning committees to take decisions in signed networks. Given an integer k, the internally stable group problem deals with finding a group of k nodes that satisfies internal stability. In this paper, we first study the computational aspects of these two problems. We first prove that both these problems are hard computationally. We then present computationally efficient algorithms for these problems that are approximate in spirit. We then show the efficacy of the proposed algorithms by using real life signed social networks. � Springer Nature Singapore Pte Ltd 2019.