The week's pick
Reseach Article
An Optimal Algorithm to Detect Balancing in Common-edge Sigraph
| 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
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
- Acharya B . D, 1980, (1980b) Applications of sigraphs in behavioral sciences, MRI Technical Report DST/HCS. .
- Acharya B. D, 1983, A characterization of consistent marked graphs, Nat. Acad. Sci. -Letters, India.
- 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.
- Acharya, B. D and Acharya, M, 1986, New algebraic models of a social system, Indian Journal of Pure and Applied Mathematics.
- Acharya, M and Sinha, D, 2005, Characterizations of line sigraphs, Nat. Acad. Sci. –Letters.
- Acharya, M and Sinha, D, 2006, Common-edge sigraphs, AKCE Int. J. Graphs Comb.
- Balbuena, C, Garcia-Vazquez, P. 2004, Edge-connectivity in Pk - path graphs, Discrete Mathematics.
- Behzad, M. and Chartrand, G. T , 1969, Line coloring of signed graphs, Elem. Math.
- Broersma, H. J. , HOEDE, C. , 1989, Path graphs, Journal of Graph Theory.
- Cartwright, D. and Harary, F. , 1956, Structural Balance: A generalization of Heider's Theory, Psych. Rev.
- Chartrand, G. T. , 1977, Graphs as Mathematical Models, Prindle, Weber and Schmidt, Inc. , Boston, Massachusetts.
- Cormen, Thomas, Leiserson, Charles. , Rivest, Ronald. , Stein, Clifford. , 2011, Introduction to algorithm, Third Edition, PHI Learning Private Limited.
- Deo, Narasing. , 1995, Graph theory with application to Engineering and Computer Science, Prentice Hall India.
- Doreian, P. , (1979/80), On the evolution of group and network structure, Social Networks.
- Doreian, P. , and Mrvar, A. , 1996, A partitioning approach in structural balance, Social Networks.
- Doreian, P. , 2002, Event sequences as generators of social network evolution, Social Networks.
- 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.
- Harary, F. , 1969, Graph Theory, Addison-Wesley Publ. Comp. , Reading, Massachusetts.
- Harary, F. , and Kabell, J. A. , 1980/81, A simple algorithm to detect balance in signed graphs, Math. Soc. Sci.
- Holland, L. W. , and Leinhardt, S. , 1977, Social structure as a network process, Zeitschrift f¨ur Soziologi´e.
- Horowitz, Ellis. , Sahni, Sartaj. , 2004, Computer Algorithm, Galgotia Publications, 2004 Edition.
- Kanetkar, Yashavant. , 2004, "Let Us C", Fifth Edition, BPB Publications.
- Kanetkar, Yashavant. , 2008, "Graphics under C", Fifth Edition, BPB publications.
- Kovchegov, V. B. , 1993, A model of dynamics of group structure of human institutions, Journal of Mathematical Sociology.
- 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.
- Kovchegov, V. B. , 2004, Application of the theory of locally interacting and product potential networks of automata to modelling balance in social groups, Preprint.
- Li, H. , Lin, Y. , 1993, On the characterization of path graphs, Journal of Graph Theory.
- Li, X. , Zhao, B. , 2004, Isomorphisms of Pk – graphs for k ? 4, Discrete Mathematics.
- 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.
- Sinha, D. , 2005, New frontiers in the theory of signed graph, Ph. D. Thesis, University of Delhi (Faculty of Technology).
- Sinha, D. , Upadhayaya, S. , Kataria, P. , 2013, Characterization of Common edge signed graphs, Applied Discrete Mathematics.
- Kulli, V. R. , 1973, On common-edge graphs, The Karnatak University Journal: Science XVIII.
- West, D. B. , 1996, Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd.
- Zasalavsky, T. , 1981, Characterizations of signed graphs, J. Graph Theory.
- Zasalavsky, T. , 1982, Signed graphs, Discrete Appl. Math
Index Terms
Keywords