An Optimal Algorithm to Detect Balancing in Common-edge Sigraph
Deepa Sinha, Anshu Sethi · International Journal of Computer Applications · 2014
A signed graph (or sigraph in short) S is a graph G in which each edge x carries a value s(x) ∈ {+1, -1} called its sign denoted specially as S = (G, s).Given a sigraph S, a new sigraph C E (S), called the common-edge sigraph of S is that sigraph whose vertex-set is the set of pairs of adjacent edges in S and two vertices of C E (S) are adjacent if the corresponding pairs of adjacent edges of S have exactly one edge in common, and the sign of the edge is the sign of the common edge.If all the edges of the sigraph S carry + sign then S is actually a graph and the corresponding commonedge sigraph is termed as the common-edge graph.In this paper, algorithms are defined to obtain a common-edge sigraph and detect whether it is balanced or not in O(n 3 ) steps which will be optimal in nature.