Research Article
Diametral Reachable Index (DRI) of a Vertex
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 49 - Issue 16 |
| Published: July 2012 |
| Authors: H. B. Walikar, Shreedevi V. Shindhe |
10.5120/7715-1174
|
H. B. Walikar, Shreedevi V. Shindhe . Diametral Reachable Index (DRI) of a Vertex. International Journal of Computer Applications. 49, 16 (July 2012), 43-47. DOI=10.5120/7715-1174
@article{ 10.5120/7715-1174,
author = { H. B. Walikar,Shreedevi V. Shindhe },
title = { Diametral Reachable Index (DRI) of a Vertex },
journal = { International Journal of Computer Applications },
year = { 2012 },
volume = { 49 },
number = { 16 },
pages = { 43-47 },
doi = { 10.5120/7715-1174 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A H. B. Walikar
%A Shreedevi V. Shindhe
%T Diametral Reachable Index (DRI) of a Vertex%T
%J International Journal of Computer Applications
%V 49
%N 16
%P 43-47
%R 10.5120/7715-1174
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Every graph has one or more diametral paths. A diametral path of a graph is a shortest path whose length is equal to the diameter of the graph. Let dv be a diametral vertex. There may be one or more diametral paths originating from dv. We want to find all the diametral paths, originating from dv. The total number of diametral paths reachable from a vertex v is called the Diametral Reachable Index of that vertex, denoted DRI(v). For any vertex v, the DRI(v)=0, if there are no diametral paths reachable from v, else we write DRI(v)=t, where t is the total number of diametral paths reachable from vertex v. An algorithm is developed to find DRI of each vertex of a graph, by modifying the DFS algorithm.
References
- Anany Levitin, Introduction to the design and analysis of Algorithms, 2nd Ed, 2008.
- Coremen. T. H, Leiserson, C. E. Rivest R. L, and C Stein, Introduction to Algorithms, 2nd Ed. MIT press, Cambridge, MA, 2001.
- Data Structures, Algorithms, and Applications in C++, Sartaj Sahni. McGraw-Hill Education, 1998.
- Distance in graphs - Fred Buckley, Frank Harary, Addison-Wesley Pub. Co. , ©1990 .
- Harary. F, Graph Theory, Addison Wesley.
- R. W. Floyd. Algorithm 97: Shortest path. Comm. ACM, 5:345, 1962.
- Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146–160.
- E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numer. Math. , 1:269-271, 1959.
- A. V. Goldberg and C. Silverstein. Implementations of Dijkstra's Algorithm Based on Multi-Level Buckets. In P. M. Pardalos, D. W. Hearn, and W. W. Hages, editors, Lecture Notes in Economics and Mathematical System 450 (Refereed Proceedings), pages 292-327. Springer Verlag, 1997.
- Boris V. Cherkassky , Andrew V. Goldberg , Craig Silverstein, Buckets, Heaps, Lists, and Monotone Priority Queues, SIAM Journal on Computing, v. 28 n. 4, p. 1326-1346, Aug. 1999 .
Index Terms
Keywords