Parallel algorithms on interval graphs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 6, pp. 451-470.
@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},
pages = {451--470},
publisher = {EDP-Sciences},
volume = {29},
number = {6},
year = {1995},
zbl = {0881.68088},
mrnumber = {1377025},
language = {en},
url = {http://www.numdam.org/item/ITA_1995__29_6_451_0/}
}
TY  - JOUR
AU  - Balayogan, V. B.
AU  - Pandu Rangan, C.
TI  - Parallel algorithms on interval graphs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1995
DA  - 1995///
SP  - 451
EP  - 470
VL  - 29
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1995__29_6_451_0/
UR  - https://zbmath.org/?q=an%3A0881.68088
UR  - https://www.ams.org/mathscinet-getitem?mr=1377025
LA  - en
ID  - ITA_1995__29_6_451_0
ER  - 
Balayogan, V. B.; Pandu Rangan, C. Parallel algorithms on interval graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 6, pp. 451-470. http://www.numdam.org/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