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

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

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