A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph

References

• Bera , D. , Pal , M. and Pal , T. K. 2003 . An optimal PRAM algorithm for a spanning tree on trapezoid graphs . Journal of Applied Mathematics and Computing , 12 : 21 – 29 .
   Google Scholar
• Cai , L. and Corneil , D. G. 1995 . Tree spanners . SIAM Journal on Discrete Mathematics , 8 : 359 – 387 .
   Web of Science ®Google Scholar
• Chen , H. C. and Wang , Y. L. 1997 . A linear time algorithm for finding depth-first spanning trees on trapezoid graphs . Information Processing Letters , 63 : 13 – 18 .
   Web of Science ®Google Scholar
• Corneil , D. G. and Kamula , P. A. 1987 . Extensions of permutation and interval graphs . Congressus Numerantium , 58 : 267 – 275 .
   Google Scholar
• Dagan , I. , Golumbic , M. C. and Pinter , R. Y. 1988 . Trapezoid graphs and their coloring . Discrete Applied Mathematics , 21 : 35 – 46 .
   Web of Science ®Google Scholar
• Gould , R. 1988 . Graph Theory , Benjamin Cummings .
   Google Scholar
• Jájá , J. 1992 . Introduction to Parallel Algorithms , Addison-Wesley .
   Google Scholar
• Kratsch , D. , Le , H. O. , Müller , H. , Prisner , E. and Wagner , D. 2003 . Additive tree spanners . SIAM Journal on Discrete Mathematics , 17 : 332 – 340 .
   Web of Science ®Google Scholar
• Kruskal , C. P. , Rudolph , L. and Snir , M. 1985 . The power of parallel prefix . IEEE Transactions on Computers , 34 : 965 – 968 .
   Web of Science ®Google Scholar
• Liang , Y. D. 1995 . Steiner set and connected domination in trapezoid graphs . Information Processing Letters , 56 : 101 – 108 .
   Web of Science ®Google Scholar