Parallel algorithms on interval graphs
Balayogan, V. B. ; Pandu Rangan, C.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 451-470 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1995-01-01
@article{ITA_1995__29_6_451_0,
     author = {Balayogan, V. B. and Pandu Rangan, C.},
     title = {Parallel algorithms on interval graphs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {29},
     year = {1995},
     pages = {451-470},
     mrnumber = {1377025},
     zbl = {0881.68088},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1995__29_6_451_0}
}

Balayogan, V. B.; Pandu Rangan, C. Parallel algorithms on interval graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) pp. 451-470. http://gdmltest.u-ga.fr/item/ITA_1995__29_6_451_0/

[BSV88] O. Berkman, B. Schieber and U. Vishkin, Some doubly logarithmic optimal algorithms based on nearest smallers, Research Report RC 14128 (#63291), IBM Research Division, Israel, 1988.

[BB87] A. A. Bertossi, and M. A. Bonuccelli, Some parallel algorithms on interval graphs, Discrete Applied Mathematics, 1987, 16, pp. 101-111. | MR 874909 | Zbl 0636.68087

[C86] R. Cole, Parallel merge sort, Proc. 27th Annual Symposium on the Foundations of Computer Science, 1986, pp. 511-516.

[GDSP90] G. D. S. Ramkumar and C. Pandu, Rangan, Parallel algorithms on interval graphs, Volume 3 in the Proc. 1990 International Conference on Parallel Processing, 1990, pp. 72-75.

[G80] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, USA, 1980. | MR 562306 | Zbl 0541.05054

[K88] P. Klein, Efficient parallel algorithms on chordal graphs, Laboratory for Computer Science, MIT, USA, 1988. Also Appeared as Chapter 8 in [R93].

[MJ88] A. Moitra and R. Johnson, Parallel algorithms for maximum matching and other problems on interval graphs, TR 88-927, Cornell University, Ithaca, USA, 1988.

[RP88] G. Ramalingam and C. Pandu, Rangan, A unified approach to domination problems on interval graphs, Information Processing Letters, 1988, 27, pp. 271-274. | MR 942582 | Zbl 0658.05040

[R85] J. H. Reif, Depth First Search is inherently sequential, Information Processing Letters, 1985, 20, pp. 229-234. | MR 801987 | Zbl 0572.68051

[R93] J. H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann, California, USA, 1993. | MR 1212591

[R76] F. S. Roberts, Discrete Mathematical Models with Applications to Social, Biological and Environmental problems, Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1976. | Zbl 0363.90002

[SW88] J. E. Savage and M. G. Wloka, A parallel algorithm for channel routing, Proceedings of WG'88, Graph-theoretic Concepts in Computer Science (published as Lecture Notes in Computer Science, Springer-Verlag, New York, 1988). | MR 1024855

[TC84] Y. H. Tsin and F. Y. Chin, Efficient parallel algorithms for a class of graph theoretic problems, SIAM Journal of Computing, 1984, 13, pp. 580-599. | MR 749708 | Zbl 0545.68060

[SG91] M. A. Sridhar and S. Goyal, Efficient parallel Computation of Hamiltonian Paths and Circuits in Interval Graphs, Proc. Int. Conf. On Parallel Processing, Vol. 3, 1991, pp. 83-90.

[K89] S. K. Kim, Optimal Parallel Algorithms on Sorted Intervals, Proc. 27th Annual Allerton Conf. on Comm., control and Computing, 1989, pp. 766-775.

[OSZ90] S. Olariu, J. L. Schwing and J. Zhang, Optimal Parallel Algorithms for Problems Modelled by a Family of Intervals, Proc. 28th Annual Allerton Conf. on Comm., Control and Computing, 1990, pp. 282-291.

[SK91] Alan P. Sprague and K. H. Kulkarni, Optimal Parallel algorithms for finding the Cut vertices and Bridges of Interval graphs, Technical report, University of Alabama, USA, June, 1991. | MR 1170882

[DC92] S. K. Das and C. C. Y. Chen, Efficient Parallel Algorithms on Interval graphs, Technical report, Department of Computer science, University of North texas, USA, 1992. | MR 1230239

[JJ92] Joseph Ja Ja, An Introduction to Parallel Algorithms, Addison Wesley, USA, 1992. | Zbl 0781.68009