Algorithmic Approach to Eccentricities, Diameters and Radii of Graphs using DFS
|
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