AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS

References

• K. Abrahamson , N. Dadoun , D. G. Kirkpatrick and T. Przytycka , A simple parallel tree contraction algorithm . Journal of Algorithms 10 ( 1989 ), 287 – 302 .
   Google Scholar
• G. S. Adhar and S. Peng , Parallel algorithm for path covering, Hamiltonian path, and Hamiltonian cycle in cographs. Proc. Internal. Conf. on Parallel Processing III ( 1990 ), 364 – 365 .
   Google Scholar
• R. J. Anderson and G. L. Miller , Deterministic parallel list ranking . Algorithmica 6 ( 1991 ), 859 – 868 .
   Google Scholar
• J. A. Bondy and U. S. R. Murty , Graph theory with applications . NorthHolland , Amsterdam , 1976 .
   Google Scholar
• R. Cole and U. Vishkin , Approximate parallel scheduling. Part I The basic technique with applications to optimal parallel list ranking in logarithmic time . SIAM Journal on Computing 17 ( 1988 ), 128 – 142 .
   Web of Science ®Google Scholar
• R. Cole and U. Vishkin , The accelerated ccntroid decomposition technique for optimal tree evaluation in logarithmic time. Algorithmica 3 ( 1988 ), 329 – 346 .
   Google Scholar
• D. G. Corncil , H. Lerchs and L. Stewart Burlingham , Complement reducible graphs. Discrete Applied Matliemalics 3 ( 1981 ), 163 – 174 .
   Google Scholar
• M. R. Garey and D. S. Johnson , Computers and intracability, a guide to the theory of NP-complete-ness.Freeman , San Francisco , 1979.
   Google Scholar
• H. Gazit , G. L. Miller and S. H. Teng , Optimal tree contraction in the EREW model. PrincetonWorkshop Book , Plenum Press , New York , 1989 .
   Google Scholar
• A. Gibbons and W. Rytter , Optimal parallel algorithms for dynamic expression evaluation and context-free recognition. Information and Computation 81 ( 1989 ), 32 – 45 .
   Google Scholar
• X. He , Efficient parallel algorithms for solving some tree problems. Proc. 24th Allerton Conf. On Communication, Control, and Computing ( 1986 ), 777 – 786 .
   Google Scholar
• R. M. Karp and V. Ramachandran , A survey of parallel algorithms for shared memory machines. In Handbook of Theoretical Computer Science , J. van Leeuwen (ed). North Holland , 1990 , 869 – 941 .
   Google Scholar
• C. P. Kruskal , L. Rudolph and M. Snir , Efficient parallel algorithms for graph problems. Algorithmica 5 ( 1990 ), 43 – 64 .
   Web of Science ®Google Scholar
• R. Lin and S. Olariu , A fast recognition algorithm for cographs. Journal of Parallel and Distributed Processing 13 ( 1991 ), 76 – 91 .
   Google Scholar
• G. L. Miller and J. Reif , Parallel tree contraction and its applications. Proc. 17th Annual Symposium on the Theory of Computing ( 1985 ), 478 – 489 .
   Google Scholar
• G. L. Miller and J. Rcif , Parallel tree contraction, Part 2 Further applications . SIAM Journal on Computing 20 ( 1991 ), 1128 – 1147 .
   Google Scholar
• S. Moran and Y. Wolfstall , Optimal covering of Cacti by vertex-disjoint paths. Dept. of Computer Science Technion , Israel , Tech. Report 501 , March 1988 .
   Google Scholar
• R. E. Tarjan and U. Vishkin , An efficient parallel biconnectivity algorithm . SIAM Journal on Computing 14 ( 1985 ), 862 – 874 .
   Web of Science ®Google Scholar
• U. Vishkin , Structural parallel algorithmics . Technical Report, UMIACS-TR-91-53 , April , 1991 .
   Google Scholar