Full Text:
<2443>
CLC number: O29
On-line Access:
Received: 2003-11-13
Revision Accepted: 2004-01-08
Crosschecked: 0000-00-00
Cited: 0
Clicked: 5137
Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs
| |||||||||||||
MISHRA P.K.. Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs[J]. Journal of Zhejiang University Science A, 2004, 5(9): 1135-1143.
@article{title="Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs",
author="MISHRA P.K.",
journal="Journal of Zhejiang University Science A",
volume="5",
number="9",
pages="1135-1143",
year="2004",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2004.1135"
}
%0 Journal Article
%T Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs
%A MISHRA P.K.
%J Journal of Zhejiang University SCIENCE A
%V 5
%N 9
%P 1135-1143
%@ 1869-1951
%D 2004
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2004.1135
TY - JOUR
T1 - Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs
A1 - MISHRA P.K.
J0 - Journal of Zhejiang University Science A
VL - 5
IS - 9
SP - 1135
EP - 1143
%@ 1869-1951
Y1 - 2004
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2004.1135
Abstract: This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.
[1] Aho, A.V., Hopcroft, J.E., Ullman, J.D., 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA.
[2] Atallah, M.J., Chen, D.Z., 1989. An optimal parallel algorithm for the minimum circle cover problem. Information Processing Letters, 32:159-165.
[3] Bertossi, A.A., 1988. Parallel circle cover algorithms. Information Processing Letters, 27:133-139.
[4] Booth, K.S., Luekher, G.S., 1976. Testing for the consecutive ones properly, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13:335-379.
[5] Chen, D.Z., Lee, D.T., 1994. Solving the All Pair Shortest-path Problem on Interval and Circular-arc Graphs. Proceedings of the 8th International Parallel Processing Symposium, Cancun, Mexico, p.224-228.
[6] Gabow, H.N., Tarjan, R.E., 1985. A linear time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30:209-221.
[7] Golumbic, M.C., 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.
[8] Gupta, U.I., Lee, D.T., Leung, J.Y.T., 1982. Efficient algorithms for interval graphs and circular-arc graphs. Networks, 12:459-467.
[9] Ibarrra, O.H., Wang, H., Zheng, Q., 1992. Minimum Cover and Single Source Shortest-path Problems for Weighted Interval Graphs and Circular-Arc Graphs. Proceeding of the 30th Annual Allerton Conference on Communication, Control and Computing, University of Illinois, Urbana, p.575-584.
[10] Lee, C.C., Lee, D.T., 1984. On a circle cover minimization problem. Information Processing Letters, 18:109-115.
[11] Mishra, P.K., Sharma, C.K., 1997. A Computational Study of the Shortest-path Algorithms in C-Programming Language. Proc. Fifth International Conference on Applications of High Performance Computing in Engineering, Santiago de Compostela, Spain.
[12] Mishra, P.K., Sharma, C.K., 2002. An efficient implementation of scaling algorithms for the shortest-paths problem. News Bulletin of Calcutta Mathematical Society, 27:342-351.
[13] Mishra, P.K., 2004. An efficient parallel algorithm for shortest-paths in planar layered digraphs. Journal of Zhejiang University SCIENCE, 5(5):518-527.
Open peer comments: Debate/Discuss/Question/Opinion
<1>
Sovan Samanta@research scholar<navosmath@gmail.com>
2011-01-25 10:28:45
Respected sir
please give the paper as it is urgent for me.I will be thank ful to you.--
sovan samantaV.U.