Research Article
Algorithmic Approach to Eccentricities, Diameters and Radii of Graphs using DFS
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 54 - Issue 18 |
| Published: September 2012 |
| Authors: Ishwar Baidari, Ravi Roogi, Shridevi Shinde |
10.5120/8664-2284
|
Ishwar Baidari, Ravi Roogi, Shridevi Shinde . Algorithmic Approach to Eccentricities, Diameters and Radii of Graphs using DFS. International Journal of Computer Applications. 54, 18 (September 2012), 1-4. DOI=10.5120/8664-2284
@article{ 10.5120/8664-2284,
author = { Ishwar Baidari,Ravi Roogi,Shridevi Shinde },
title = { 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 },
doi = { 10.5120/8664-2284 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A Ishwar Baidari
%A Ravi Roogi
%A Shridevi Shinde
%T Algorithmic Approach to Eccentricities, Diameters and Radii of Graphs using DFS%T
%J International Journal of Computer Applications
%V 54
%N 18
%P 1-4
%R 10.5120/8664-2284
%I Foundation of Computer Science (FCS), NY, USA
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
Index Terms
Keywords