A novel Approach to Compute Steiner point in Graph: Application for Network Design
DOI:
https://doi.org/10.26438/ijcse/v5i9.224231Keywords:
Graph, Network, Cable length, Steiner point, data structuresAbstract
A Graph has two main components: Vertices and Edges. The vertices are connected using edges. There are two types of graphs, directed and undirected. The major application of graph is representing network on paper. The cost involved in converting paper based network to actual cable based network is majorly controlled by cables required for connection. The cost can be reduced if the length of cable can be reduced. The paper describes the methodology to compute Steiner point. Using Steiner point, it is possible to modify the position of vertices, so as to reduce the cable length, keeping the vertex connectivity intact. The paper describes implementation of Steiner point on graph with number of vertices as 3, 4, 5 and 6. The presented work can be extended for graph with any number of vertices. It is an optimization approach to reduce the cable size and cost of network implementation.
References
Germander Soothill (April 27, 2010). The Euclidean Steiner Problem.
Marshall W. Bern and Ronald L. Graham (January 1989). The shortest network problem, Scientific American.
E. N. Gilbert and H. O. Pollak (Volume 16 no. 1, January 1968). SIAM Journal of Applied Mathematics.
M.B.Chandak, R.Dharaskar, “Natural Language processing based context sensitive, content specific architecture and its speech based implementation for smart homes, International Journal of Smart homes, 4(2), 1-10, 2010.
F.Riaz, K.M.Ali, “Application of graph theory in Computer Science” Third International Conference on Computational Intelligence, Communication Systems and Networks.
H.Selim, P.Chopade, “Structural analysis and interactive visualization of large scale big data networks” IEEE 11th International Conference on Networking, Sensing and Control.
N.Lakshmi Prasanna, “Application of Graph labelling in communication networks” Oriental Journal of Computer Science and Technology” ISSN-09724-6471
Dr. S.M. Hegde, “Labeled graphs and Digraphs: Theory and Applications”, 12-01-2012 Research Promotion Workshop on IGGA
http://www.britinaca.com/bps/additionalcontent/18/3 3373769/concepts-of-graph-theory-relevant-to-Adhoc- Networks.
T. Suel and J. Yuan. Compressing the graph structure of the web. In Proceedings of the IEEE Data Compression Conference, 2001.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.1: Representations of graphs", Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7
Balakrishnan, V. K. (1997-02-01). Graph Theory (1st ed.). McGraw-Hill. ISBN 0-07-005489-4.
Svetlin Nakov, Fundamentals of Computer Programming with C#
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
