Research Article
An Algorithm for Testing a Signed Graph for Balance
|
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
|
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
Keywords