Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] |

¡@

**F. R. Hsu, M. K. Shan ^{**}, H. S. Chao^{+} and R. C. T. Lee^{++}**

Department of Information Engineering and Computer Science

Feng Chia University

Taichung, 407 Taiwan

E-mail: frhsu@fcu.edu.tw

National Chengchi Unviersity

Taipei, 116 Taiwan

National Chi Nan University

Nantou, 545 Taiwan

In this paper, we consider some shortest path related problems on interval and circular-
arc graphs. For the all-pair shortest path query problem on interval and circular-arc
graphs, instead of using the sophisticated technique, we propose simple parallel algorithms
using only the parallel prefix and suffix computations and the Euler tour technique.
Our preprocessing algorithms run in *O*(log *n*) time using *O*(*n*log *n*) processors.
Using the data structure constructed by our preprocessing algorithms, a query of the
length of a shortest path between any two vertices can be answered in constant time by
using a single processor. For the hinge vertex problem on interval graphs, we propose an
*O*(log *n*) time algorithm using *O*(*n*log *n*
) processors. It leads to a linear time sequential
algorithm. Our algorithms work on the EREW PRAM model.

*
Keywords:
*
parallel algorithms, EREW PRAM, all-pair shortest path, hinge vertex, interval
graph

Retrieve PDF document (**200505_08.pdf**)

Received December 30, 2002; revised April 26, 2004; accepted October 20, 2004.

Communicated by Jeremy P. Spinrad.
^{*}This paper was supported in part by the National Science Council of Taiwan, R.O.C., under grand NSC
88-2213-E-126-005.