Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs
作者： F. R. Hsu , Yaw-Ling Lin , Yin-Te Tsai
关键词:
摘要: In this paper, we consider parallel algorithms for shortest paths and related problems on trapezoid graphs under the CREW PRAM model. Given a graph with its corresponding diagram, present solving following problems: For single-source path problem, algorithm runs in O(log n) time using O(n) processors space. all-pair query after spending preprocessing O(n log space processors, can answer δ) one processor. Here δ denotes distance between two queried vertices. minimum cardinality Steiner set We also extend our results to generalized graphs. The problem d-trapezoid circular both be solved n d) O(nd) O(d2n= processors. answered O(d processor O(nd
springer.com
sci-hub.st 参考文章(7)
Selim G. Akl, Parallel computation: models and methods Prentice-Hall, Inc.. ,(1997)
Y.Daniel Liang, Steiner set and connected domination in trapezoid graphs Information Processing Letters. ,vol. 56, pp. 101- 108 ,(1995) , 10.1016/0020-0190(95)00118-V
Ido Dagan, Martin Charles Golumbic, Ron Yair Pinter, Trapezoid graphs and their coloring Discrete Applied Mathematics. ,vol. 21, pp. 35- 46 ,(1988) , 10.1016/0166-218X(88)90032-7
Dieter Kratsch, Ton Kloks, Haiko Muller, Measuring the vulnerability for classes of intersection graphs Discrete Applied Mathematics. ,vol. 77, pp. 259- 270 ,(1997) , 10.1016/S0166-218X(96)00133-3
Danny Z. Chen, D. T. Lee, R. Sridhar, Chandra N. Sekharan, Solving the all-pair shortest path query problem on interval and circular-arc graphs Networks. ,vol. 31, pp. 249- 258 ,(1998) , 10.1002/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D
O.H. Ibarra, Q. Zheng, An optimal shortest path parallel algorithm for permutation graphs Journal of Parallel and Distributed Computing. ,vol. 24, pp. 94- 99 ,(1995) , 10.1006/JPDC.1995.1009
Carsten Flotow, On powers of m -trapezoid graphs Discrete Applied Mathematics. ,vol. 63, pp. 187- 192 ,(1995) , 10.1016/0166-218X(95)00062-V