Open Access   Article Go Back

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

S.K. Reddy Avula1 , P.S.K. Reddy2

Section:Review Paper, Product Type: Journal Paper
Volume-4 , Issue-9 , Page no. 33-35, Sep-2016

Online published on Sep 30, 2016

Copyright © S.K. Reddy Avula, P.S.K. Reddy . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: S.K. Reddy Avula, P.S.K. Reddy, “An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph,” International Journal of Computer Sciences and Engineering, Vol.4, Issue.9, pp.33-35, 2016.

MLA Style Citation: S.K. Reddy Avula, P.S.K. Reddy "An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph." International Journal of Computer Sciences and Engineering 4.9 (2016): 33-35.

APA Style Citation: S.K. Reddy Avula, P.S.K. Reddy, (2016). An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph. International Journal of Computer Sciences and Engineering, 4(9), 33-35.

BibTex Style Citation:
@article{Avula_2016,
author = {S.K. Reddy Avula, P.S.K. Reddy},
title = {An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {9 2016},
volume = {4},
Issue = {9},
month = {9},
year = {2016},
issn = {2347-2693},
pages = {33-35},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=1051},
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=1051
TI - An Algorithm with Optimal Time and Space Efficiency to Detect Balance of a Signed Graph
T2 - International Journal of Computer Sciences and Engineering
AU - S.K. Reddy Avula, P.S.K. Reddy
PY - 2016
DA - 2016/09/30
PB - IJCSE, Indore, INDIA
SP - 33-35
IS - 9
VL - 4
SN - 2347-2693
ER -

VIEWS PDF XML
1816 1646 downloads 1489 downloads
  
  
           

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.

Key-Words / Index Term

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

References

[1] 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.
[2] Harary F - �Graph Theory�, Addison Wesley, 1969.
[3] Harary F, �On the Notion of Balance of a Signed Graph�, Michigan Mathematical Journal, 2, Pg. No: 143 � 146, 1953 - 1954.
[4] Heider F, �Attitude and Cognitive Organization�, Journal of Psych., 21, Pg. No: 107 � 112, 1946.
[5] 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.
[6] Arvind Srinivasan, �Local Balancing influences global structure in Social Networks�, PNAS, Vol. 108, No. 5, Pg. No: 1751 � 1752, 2011.
[7] 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.
[8] 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.
[9] Zaslavsky T, �Charecterization of Signed Graph�, Journal of Graph Theory, 5, Pg. No: 401 � 406, 1981.
[10] Knuth D, �Fundamental Algorithms�, Vol. I of the Art of Computer Programming, MA: Addision � Wesley, 2nd Edition, 1973.