Logarithmic time NC algorithms for comparability graphs and circle graphs

1. G. S. Adhar and S. Peng. Parallel algorithms for cographs recognition and applications. In F. Dehne, J.-R. Sack, and N. Santoro, editors, Proc. Workshop on Algorithms and Data Structures (Carleton University, Ottawa, Ontario, Canada, August 17–19), Lecture Notes in Computer Science, Vol. 382, pages 335–351. Springer-Verlag, 1989.

   Google Scholar 

2. G. S. Adhar and S. Peng. Parallel algorithms for cographs and parity graphs with applications. J. Algorithms, 11(2):252–284, June 1990.

   Article  Google Scholar 

3. S. G. Akl. The Design and Analysis of Parallel Algorithms. Prentice Hall, Englewood Cliffs, N.J., 1989.

   Google Scholar 

4. L. Chen and Y. Yesha. Parallel testing for the consecutive ones property and transformable convex bipartite graphs and finding a maximum matching. In Proc. 27th Ann. Allerton Conf. on Communication, Control, and Computing (Monticello, Illinois, Sept. 27–29), pages 756–765. University of Illinois at Urbana-Champaign, 1989.

   Google Scholar 

5. L. Chen and Y. Yesha. Parallel recognition of the consecutive ones property with applications. J. Algorithms, 12 (3), September 1991. (scheduled)

   Google Scholar 

6. D. G. Corneil, H. Lerchs, and L. Stewart Burlingham. Complement reducible graphs. Discrete Applied Mathematics, 3(3):163–174, 1981.

   Article  Google Scholar 

7. S. Even and A. Itai. Queues, stacks and graphs. In Z. Kohavi and A. Paz, editors, Theory of Machines and Computations, pages 71–86. Academic Press, New York, 1971.

   Google Scholar 

8. C. P. Gabor, W.-L. Hsu, and K. J. Supowit. Recognizing circle graphs in polynomial time. In Proc. 26th Ann. Symp. on Foundations of Computer Science, pages 106–116. IEEE Computer Society, 1985.

   Google Scholar 

9. F. Gavril. Algorithms for a maximum clique and a minimum independent set of a circle graph. Networks, 3:261–273, 1973.

   Google Scholar 

10. M. Goldberg and T. Spencer. A new parallel algorithm for the maximal independent set problem. In Proc. 28th Ann. Symp. on Foundations of Computer Science, pages 161–165. IEEE Computer Society, 1987.

    Google Scholar 

11. M. Goldberg and T. Spencer. Constructing a maximal independent set in parallel. SIAM J. on Discr. Math., 2(3):322–328, August 1989.

    Article  Google Scholar 

12. M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Computer Science and Applied Mathematics. Academic Press, New York, 1980.

    Google Scholar 

13. D. Helmbold and E. Mayr. Perfect graphs and parallel algorithms. In Proc. International Conference on Parallel Processing, pages 853–860, 1986.

    Google Scholar 

14. W.-L. Hsu. Maximum weight clique algorithms for circular-arc graphs and circle graphs. SIAM Journal on Computing, 14:224–231, 1985.

    Google Scholar 

15. D. S. Johnson. The NP-completeness column: an ongoing guide. J. Algorithms, 6:434–451, 1985.

    Article  Google Scholar 

16. R. M. Karp and A. Wigderson. A fast parallel algorithm for the maximal independent set problem. Journal of the ACM, 32(4):762–773, 1985.

    Google Scholar 

17. L. Lovász. A characterization of perfect graphs. J. Combin. Theory B, 13:95–98, 1972.

    Google Scholar 

18. M. Luby. A simple parallel algorithm for the maximal independent set problem. In Proc. 17th Annual Symposium on Theory of Computing (Providence, RI), pages 1–10. Association for Computing Machinery, 1985.

    Google Scholar 

19. S. Masuda, K. Nakajima, T. Kashiwabara, and T. Fujisawa. Efficient algorithms for finding maximum cliques of an overlap graph. Networks, 20:157–171, 1990.

    Google Scholar 

20. M. B. Novick. Logarithmic time parallel algorithms for comparability and interval graphs. Technical Report TR89-1015, Cornell University, June 1989.

    Google Scholar 

21. A. Pnueli, A. Lempel, and S. Even. Transitive orientation of graphs and identification of permutation graphs. Canad. J. Math., 23:160–175, 1971.

    Google Scholar 

22. C. Rhee, S. K. Dhall, and S. Lakshmivarahan. An NC algorithm for finding a maximum weight clique on a circle graph. In Proc. 27th Ann. Allerton Conf. on Communication, Control, and Computing (Monticello, Illinois, Sept. 27–29), pages 776–777. University of Illinois at Urbana-Champaign, 1989.

    Google Scholar 

23. D. Rotem and J. Urrutia. Finding maximum cliques in circle graphs. Networks, 11(3):269–278, 1981.

    Google Scholar 

24. R. E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862–874, November 1985.

    MathSciNet  Google Scholar 

Download references