CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Diametral Reachable Index (DRI) of a Vertex

by H. B. Walikar, Shreedevi V. Shindhe
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 49 - Number 16
Year of Publication: 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 },
issue_date = { July 2012 },
volume = { 49 },
number = { 16 },
month = { July },
year = { 2012 },
issn = { 0975-8887 },
pages = { 43-47 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume49/number16/7715-1174/ },
doi = { 10.5120/7715-1174 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:46:50.596434+05:30
%A H. B. Walikar
%A Shreedevi V. Shindhe
%T Diametral Reachable Index (DRI) of a Vertex
%J International Journal of Computer Applications
%@ 0975-8887
%V 49
%N 16
%P 43-47
%D 2012
%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
  1. Anany Levitin, Introduction to the design and analysis of Algorithms, 2nd Ed, 2008.
  2. Coremen. T. H, Leiserson, C. E. Rivest R. L, and C Stein, Introduction to Algorithms, 2nd Ed. MIT press, Cambridge, MA, 2001.
  3. Data Structures, Algorithms, and Applications in C++, Sartaj Sahni. McGraw-Hill Education, 1998.
  4. Distance in graphs - Fred Buckley, Frank Harary, Addison-Wesley Pub. Co. , ©1990 .
  5. Harary. F, Graph Theory, Addison Wesley.
  6. R. W. Floyd. Algorithm 97: Shortest path. Comm. ACM, 5:345, 1962.
  7. Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146–160.
  8. E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numer. Math. , 1:269-271, 1959.
  9. 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.
  10. 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

Computer Science
Information Sciences

Keywords

DRI diametral paths diametral reachable index diametral vertex

Powered by PhDFocusTM