Research Article

An Algorithm for Testing a Signed Graph for Balance

by  Ioannis S. Xezonakis, Danai Xezonaki
journal cover
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 184 - Issue 11
Published: May 2022
Authors: Ioannis S. Xezonakis, Danai Xezonaki
10.5120/ijca2022922089
PDF

Ioannis S. Xezonakis, Danai Xezonaki . An Algorithm for Testing a Signed Graph for Balance. International Journal of Computer Applications. 184, 11 (May 2022), 41-44. DOI=10.5120/ijca2022922089

                        @article{ 10.5120/ijca2022922089,
                        author  = { Ioannis S. Xezonakis,Danai Xezonaki },
                        title   = { An Algorithm for Testing a Signed Graph for Balance },
                        journal = { International Journal of Computer Applications },
                        year    = { 2022 },
                        volume  = { 184 },
                        number  = { 11 },
                        pages   = { 41-44 },
                        doi     = { 10.5120/ijca2022922089 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }
                        %0 Journal Article
                        %D 2022
                        %A Ioannis S. Xezonakis
                        %A Danai Xezonaki
                        %T An Algorithm for Testing a Signed Graph for Balance%T 
                        %J International Journal of Computer Applications
                        %V 184
                        %N 11
                        %P 41-44
                        %R 10.5120/ijca2022922089
                        %I Foundation of Computer Science (FCS), NY, USA
Abstract

A signed graph consists of a graph together with a sign characterizing each vertex. A fundamental concept of signed graphs is that of balance. In this paper a programming algorithm is presented in order to detect balance in signed graphs. The algorithm traverses each vertex at most once and uses two stacks for the implementation, each having a size of at most the number of vertices of the graph. Moreover, the graph need not be stored in computer's memory.

References
  • F. Harary, and J. A. Kabell, 1980. A simple algorithm to detect balance in signed graphs. Mathematical Social Scienses 1, 131-136.
  • F. Harary, 1953-1954. On the Notion of Balance of a Signed Graph. Michigan Mathematical Journal 2, 143-146.
  • F. Harary, R.Z. Norman, and D. Cartwright, 1965. Structural Models: An Introduction to the Theory of Directed Graphs. Wiley.
  • T. Zaslavsky, 1981. Characterization of Signed Graphs. Journal of Graph Theory, 5, 401-406.
  • C. Hoede, 1992. A Characterization of Consistent Marked Graphs. Journal of Graph Theory, 16(1), 17-23.
  • F. Heider, 1946. Attitudes and Cognitive Organization. The Journal of Psychology, 21, 107-112.
  • B. Vasanthi et al., 2015. Applications of Signed Graphs to Portfolio Turnover Analysis. Procedia – Social and Behavioral Sciences, 211, 1203-1209.
  • E. Loukakis, 2003. A Dynamic Programming Algorithm to Test a Signed Graph for Balance. Intern. J. Computer Math., 80(4), 499-507.
  • S. Hameed et al., 2020. Signed Distance in Signed Graphs. Linear Algebra and its Applications, 608, 236-247.
  • T. V. Shijin et al., 2022. On the powers of signed graphs. Communications in Combinatorics and Optimization. 7 (1), 45-51.
Index Terms
Computer Science
Information Sciences
No index terms available.
Keywords

Balanced graphs Signed graphs

Powered by PhDFocusTM