An nc algorithm to recognize hhd-free graphs

References

• Berge , C. and Chvátal , V. 1984 . “ Topics on perfect graphs ” . In Annals of Discrete Mathematics , Vol. 21 , Amsterdam : North-Holland .
   Google Scholar
• Brent , R. P. 1974 . The parallel evaluation of general arithmetic expressions . JACM , 21 : 201 – 208 .
   Google Scholar
• Chandrasekharan , N. and Iyengar , S. S. 1988 . NC algorithms for recognizing chordal graphs and k-trees . IEEE Transactions on Computers , 37 : 1178 – 1183 .
   Google Scholar
• Chvátal , V. , Hoàng , C. , Mahadev , N. and De Werra , D. 1987 . Four classes of perfectly orderable graphs . Journal of Graph Theory , 7 : 481 – 495 .
   Google Scholar
• Dirac , G. A. 1961 . On rigid circuit graphs . Abh. Math. Sem. Univ. Hamburg , 25 : 71 – 76 .
   Google Scholar
• Edenbrandt A. Combinatorial Problems in Matrix Computation Cornell University Ithaca, N.Y. 1985 Ph.D. Thesis
   Google Scholar
• Golumbic , M. C. 1980 . Algorithmic Graph Theory and Perfect Graphs , New York : Academic Press .
   Google Scholar
• Helmbold , D. and Mayr , E. 1986 . Proc. IEEE Int. Conf. on Parallel Processing . Perfect graphs and parallel algorithms . Aug 1986 . pp. 853 – 860 .
   Google Scholar
• Hoàng , C. and Khouzam , N. On brittle graphs . Journal of Graph Theory , to appear
   Google Scholar
• Jamison , B. and Olariu , S. 1988 . On the semi-perfect elimination . Advances in Applied Mathematics , 9 : 364 – 376 .
   Google Scholar
• Kozen , D. , Vazirani , U. and Vazirani , V. 1985 . Proc. of the 5th Conf. on FST and TCS, New Delhi . NC Algorithms for comparability graphs, Interval graphs and testing the unique perfect matching . 1985 . pp. 496 – 503 .
   Google Scholar
• Naor , J. , Naor , M. and Schaffer , A. 1985 . Proc. of the Symposium on Theory of Computing . Fast parallel algorithms for chordal graphs . May 1985 , New York City. pp. 355 – 362 .
   Google Scholar
• Olariu , S. 1986 . Doctoral Dissertation, School of Computer Science , Montreal : McGill University .
   Google Scholar
• Olariu , S. and Randall , J. 1989 . Welsh-Powell opposition graphs . Information Processing Letters , 31 : 43 – 46 .
   Google Scholar
• Pippenger , N. 1979 . “ On simultaneous resource bounds ” . In Proc. of the 20th IEEE Symposium on Foundations of Computer Science , IEEE Press .
   Google Scholar
• Rose , D. , Tarjan , R. and Lueker , G. 1976 . Algorithmic aspects of vertex elimination on graphs . SIAM J. Comput. , 5 : 266 – 283 .
   Google Scholar
• Shiloah , Y. and Vishkin , U. 1982 . An O(log n) parellel connectivity algorithm . J. Algorithms , 3 : 57 – 67 .
   Google Scholar
• Shyu , W. 1988 . A fast parallel algorithm for cographs a manuscript
   Google Scholar
• Vishkin U. Synchronous parallel computation—A survey Courant Institute, NYU 1983 TR 71, Dept. of Computer Science
   Google Scholar
• Vishkin , U. 1983 . Implementation of simultaneous memory accesses in models that forbid it . J. Algorithms , 4 : 45 – 50 .
   Web of Science ®Google Scholar