An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph - Avula, Sashi Kanth Reddy; Siva Kota Reddy, P (International Journal of Computer Sciences and Engineering, 2025)
A Signed Graph H = (G, σ) where G is a graph G = (V, E) and σ is a sign function σ =(+, -). When talk about a signed graph, the main focus is on its balance. In this paper we propose a dynamic programming algorithm based on depth-first search graph traversing which detects the balance in the signed graph. The proposed algorithm traverses every edge of the input signed graph at most once. The implementation of the proposed algorithm will use two linear lists (arrays), one of length |V| and the other of length (|V|+1)/2. Hence the algorithm will work much efficiently with respect to time complexity and space complexity.