Call for Paper - March 2023 Edition
IJCA solicits original research papers for the March 2023 Edition. Last date of manuscript submission is February 20, 2023. Read More

Algorithmic Approach to Eccentricities, Diameters and Radii of Graphs using DFS

Print
PDF
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 54 - Number 18
Year of Publication: 2012
Authors:
Ishwar Baidari
Ravi Roogi
Shridevi Shinde
10.5120/8664-2284

Ishwar Baidari, Ravi Roogi and Shridevi Shinde. Article: Algorithmic Approach to Eccentricities, Diameters and Radii of Graphs using DFS. International Journal of Computer Applications 54(18):1-4, September 2012. Full text available. BibTeX

@article{key:article,
	author = {Ishwar Baidari and Ravi Roogi and Shridevi Shinde},
	title = {Article: Algorithmic Approach to Eccentricities, Diameters and Radii of Graphs using DFS},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {54},
	number = {18},
	pages = {1-4},
	month = {September},
	note = {Full text available}
}

Abstract

Let G = (V, E) be a graph. The distance d (u, v) between two nodes u and v is the length of the shortest path between them. The eccentricity E (v) of a graph vertex v in connected graph G is the maximum distance between v and any other vertex u of G. i. e. maxu V{ d (u, v) }. The diameter of the graph is a graph the longest shortest path between any two graph vertices (u ,v) of a graph i. e. Diam (G) = max { E (v)/ v V}. The minimum eccentricity of a graph is radius i. e. Rad (G) = min { E (v)/ v V}. In this paper we propose algorithms for finding eccentricity diameter and radius of a tree using DFS.

References

  • A note on Eccentricities, diameters, and radii Bang Ye Wu Kun–Mao Chao
  • Alan Gibbons, Algorithmic Graph Theory. Cambridge University Press. 1999
  • Lich – Hsing Hsu and Cheng- kuan Lin Graph Theory and Interconnection Networks. CRC Press 2009.
  • . Alfred V Aho, John E, Hopcroft and Jeffrey D. Ullman Data structures and Algorithms. Pearson Education 2006.
  • Thomas H Cormen Charles E Leiserson and Ronald L, Rivest. Algorithms PHI 2001.
  • Geir Agnarsson, Raymond Greenlaw. Graph Theory Modeling Applications and Algorithms.
  • Dieter Jungnickel Graphs Networks and Algorithms Springer 2006.
  • E COCKAYNE and S. GODDMAN and . HEDETINIEMI. A Liner Algorithm for the Domination Number of a Tree
  • B. S. Panda and D. Pradhan. Locally Connected Spanning Trees in Cographs, Complements of Bipartite Graph and Doubly Chordal Graph.
  • Gary chartarand, Ortrud R Oellermann, Applied and Algorithmic Graph Theory Mc Graw-Hill Inc 1993