CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

An Optimal Algorithm to Detect Balancing in Common-edge Sigraph

by Deepa Sinha, Anshu Sethi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 93 - Number 10
Year of Publication: 2014
Authors: Deepa Sinha, Anshu Sethi
10.5120/16251-5856

Deepa Sinha, Anshu Sethi . An Optimal Algorithm to Detect Balancing in Common-edge Sigraph. International Journal of Computer Applications. 93, 10 ( May 2014), 19-25. DOI=10.5120/16251-5856

@article{ 10.5120/16251-5856,
author = { Deepa Sinha, Anshu Sethi },
title = { An Optimal Algorithm to Detect Balancing in Common-edge Sigraph },
journal = { International Journal of Computer Applications },
issue_date = { May 2014 },
volume = { 93 },
number = { 10 },
month = { May },
year = { 2014 },
issn = { 0975-8887 },
pages = { 19-25 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume93/number10/16251-5856/ },
doi = { 10.5120/16251-5856 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:15:27.384566+05:30
%A Deepa Sinha
%A Anshu Sethi
%T An Optimal Algorithm to Detect Balancing in Common-edge Sigraph
%J International Journal of Computer Applications
%@ 0975-8887
%V 93
%N 10
%P 19-25
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

A signed graph (or sigraph in short) S is a graph G in which each edge x carries a value s(x) ? {+1, ?1} called its sign denoted specially as S = (G, s). Given a sigraph S, a new sigraph CE(S), called the common-edge sigraph of S is that sigraph whose vertex-set is the set of pairs of adjacent edges in S and two vertices of CE(S) are adjacent if the corresponding pairs of adjacent edges of S have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph S carry + sign then S is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, algorithms are defined to obtain a common-edge sigraph and detect whether it is balanced or not in O(n3) steps which will be optimal in nature.

References
  1. Acharya B . D, 1980, (1980b) Applications of sigraphs in behavioral sciences, MRI Technical Report DST/HCS. .
  2. Acharya B. D, 1983, A characterization of consistent marked graphs, Nat. Acad. Sci. -Letters, India.
  3. Acharya, B. D and Acharya, M, 1983, A graph-theoretical model for the analysis of intergroup stability in a social system, Manuscript. In: A mathematical bibliography of signed and gain graphs and allied areas, VII Edition.
  4. Acharya, B. D and Acharya, M, 1986, New algebraic models of a social system, Indian Journal of Pure and Applied Mathematics.
  5. Acharya, M and Sinha, D, 2005, Characterizations of line sigraphs, Nat. Acad. Sci. –Letters.
  6. Acharya, M and Sinha, D, 2006, Common-edge sigraphs, AKCE Int. J. Graphs Comb.
  7. Balbuena, C, Garcia-Vazquez, P. 2004, Edge-connectivity in Pk - path graphs, Discrete Mathematics.
  8. Behzad, M. and Chartrand, G. T , 1969, Line coloring of signed graphs, Elem. Math.
  9. Broersma, H. J. , HOEDE, C. , 1989, Path graphs, Journal of Graph Theory.
  10. Cartwright, D. and Harary, F. , 1956, Structural Balance: A generalization of Heider's Theory, Psych. Rev.
  11. Chartrand, G. T. , 1977, Graphs as Mathematical Models, Prindle, Weber and Schmidt, Inc. , Boston, Massachusetts.
  12. Cormen, Thomas, Leiserson, Charles. , Rivest, Ronald. , Stein, Clifford. , 2011, Introduction to algorithm, Third Edition, PHI Learning Private Limited.
  13. Deo, Narasing. , 1995, Graph theory with application to Engineering and Computer Science, Prentice Hall India.
  14. Doreian, P. , (1979/80), On the evolution of group and network structure, Social Networks.
  15. Doreian, P. , and Mrvar, A. , 1996, A partitioning approach in structural balance, Social Networks.
  16. Doreian, P. , 2002, Event sequences as generators of social network evolution, Social Networks.
  17. Harary, F. , Norman, R. Z. , Cartwright, R. W. , 1965, Structural Models: An Introduction to the Theory of Directed Graphs, Wiley Inter Science, Inc. , New York.
  18. Harary, F. , 1969, Graph Theory, Addison-Wesley Publ. Comp. , Reading, Massachusetts.
  19. Harary, F. , and Kabell, J. A. , 1980/81, A simple algorithm to detect balance in signed graphs, Math. Soc. Sci.
  20. Holland, L. W. , and Leinhardt, S. , 1977, Social structure as a network process, Zeitschrift f¨ur Soziologi´e.
  21. Horowitz, Ellis. , Sahni, Sartaj. , 2004, Computer Algorithm, Galgotia Publications, 2004 Edition.
  22. Kanetkar, Yashavant. , 2004, "Let Us C", Fifth Edition, BPB Publications.
  23. Kanetkar, Yashavant. , 2008, "Graphics under C", Fifth Edition, BPB publications.
  24. Kovchegov, V. B. , 1993, A model of dynamics of group structure of human institutions, Journal of Mathematical Sociology.
  25. Kovchegov, V. B. , 1994, A principle of nonergodicity for modeling of the human groups by nets of probability automata, Proceeding of the 14th IMACS World Conference on Computational and Applied Mathematics.
  26. Kovchegov, V. B. , 2004, Application of the theory of locally interacting and product potential networks of automata to modelling balance in social groups, Preprint.
  27. Li, H. , Lin, Y. , 1993, On the characterization of path graphs, Journal of Graph Theory.
  28. Li, X. , Zhao, B. , 2004, Isomorphisms of Pk – graphs for k ? 4, Discrete Mathematics.
  29. Lehot, P. G. H. , 1974, An optimal algorithm to detect a line graph and output its root graph, Journal of the Association for Computing Machinery.
  30. Sinha, D. , 2005, New frontiers in the theory of signed graph, Ph. D. Thesis, University of Delhi (Faculty of Technology).
  31. Sinha, D. , Upadhayaya, S. , Kataria, P. , 2013, Characterization of Common edge signed graphs, Applied Discrete Mathematics.
  32. Kulli, V. R. , 1973, On common-edge graphs, The Karnatak University Journal: Science XVIII.
  33. West, D. B. , 1996, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd.
  34. Zasalavsky, T. , 1981, Characterizations of signed graphs, J. Graph Theory.
  35. Zasalavsky, T. , 1982, Signed graphs, Discrete Appl. Math
Index Terms

Computer Science
Information Sciences

Keywords

Algorithm sigraph common-edge graph common-edge sigraph balanced signed graph.

Powered by PhDFocusTM