An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph

Authors

  • Avula SKR Research Scholar, Department of Computer Science, JAIN University, Bangalore
  • P Siva Kota Reddy Department of Mathematics, Siddaganga Institute of Technology, Tumkur

Keywords:

Signed Graph, linear lists, dynamic programming, time complexity, space complexity, balance

Abstract

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.

References

E. Loukakis, “A Dynamic Programming Algorithm to test a signed Graph for Balance”, International Journal of Computer Maths, Vol 80[4], Pg. No: 499 – 507, 2003.

Harary F - “Graph Theory”, Addison Wesley, 1969.

Harary F, “On the Notion of Balance of a Signed Graph”, Michigan Mathematical Journal, 2, Pg. No: 143 – 146, 1953 - 1954.

Heider F, “Attitude and Cognitive Organization”, Journal of Psych., 21, Pg. No: 107 – 112, 1946.

Giuseppe Facchetti, G. Iacono, C Altafini, “Computing Global Structural Balance in large-scale Signed Social Networks”, PNAS, vol. 108, N0. 52, Pg.No: 20953 – 20958, 2011.

Arvind Srinivasan, “Local Balancing influences global structure in Social Networks”, PNAS, Vol. 108, No. 5, Pg. No: 1751 – 1752, 2011.

T. H. Cormen, C. E. Leisersom, R. L. Riveso, C. Stein, “Introduction to Algorithms”, Prentice Hall of India, 2nd Edition, Pg. No: 540 -548, 2003.

Shi C J and Brzozowski, J A, “A Characterization of Signed Hypergraphs and its Applications to VLSI via Minimization and Logic Synthesis”, Discrete Applied Mathematics, 90, Pg. No: 223,243, 1999.

Zaslavsky T, “Charecterization of Signed Graph”, Journal of Graph Theory, 5, Pg. No: 401 – 406, 1981.

Knuth D, “Fundamental Algorithms”, Vol. I of the Art of Computer Programming, MA: Addision – Wesley, 2nd Edition, 1973.

Downloads

Published

2025-11-11

How to Cite

[1]
S. K. R. Avula and P. Siva Kota Reddy, “An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph”, Int. J. Comp. Sci. Eng., vol. 4, no. 9, pp. 33–35, Nov. 2025.

Issue

Vol. 4 No. 9 (2016): IJCSE September Edition

Section

Review Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.