Parallel algorithms on interval graphs

V. B. Balayogan; C. Pandu Rangan

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1995)

  • Volume: 29, Issue: 6, page 451-470
  • ISSN: 0988-3754

How to cite


Balayogan, V. B., and Pandu Rangan, C.. "Parallel algorithms on interval graphs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 29.6 (1995): 451-470. <>.

author = {Balayogan, V. B., Pandu Rangan, C.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {depth first search; breadth first search trees},
language = {eng},
number = {6},
pages = {451-470},
publisher = {EDP-Sciences},
title = {Parallel algorithms on interval graphs},
url = {},
volume = {29},
year = {1995},

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
PB - EDP-Sciences
VL - 29
IS - 6
SP - 451
EP - 470
LA - eng
KW - depth first search; breadth first search trees
UR -
ER -


  1. [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. 
  2. [BB87] A. A. BERTOSSI, and M. A. BONUCCELLI, Some parallel algorithms on interval graphs, Discrete Applied Mathematics, 1987, 16, pp. 101-111. Zbl0636.68087MR874909
  3. [C86] R. COLE, Parallel merge sort, Proc. 27th Annual Symposium on the Foundations of Computer Science, 1986, pp. 511-516. 
  4. [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. 
  5. [G80] M. C. GOLUMBIC, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, USA, 1980. Zbl0541.05054MR562306
  6. [K88] P. KLEIN, Efficient parallel algorithms on chordal graphs, Laboratory for Computer Science, MIT, USA, 1988. Also Appeared as Chapter 8 in [R93]. 
  7. [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. 
  8. [RP88] G. RAMALINGAM and C. PANDU, RANGAN, A unified approach to domination problems on interval graphs, Information Processing Letters, 1988, 27, pp. 271-274. Zbl0658.05040MR942582
  9. [R85] J. H. REIF, Depth First Search is inherently sequential, Information Processing Letters, 1985, 20, pp. 229-234. Zbl0572.68051MR801987
  10. [R93] J. H. REIF, Synthesis of Parallel Algorithms, Morgan Kaufmann, California, USA, 1993. MR1212591
  11. [R76] F. S. ROBERTS, Discrete Mathematical Models with Applications to Social, Biological and Environmental problems, Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1976. Zbl0363.90002
  12. [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). MR1024855
  13. [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. Zbl0545.68060MR749708
  14. [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. 
  15. [K89] S. K. KIM, Optimal Parallel Algorithms on Sorted Intervals, Proc. 27th Annual Allerton Conf. on Comm., control and Computing, 1989, pp. 766-775. 
  16. [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. 
  17. [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. Zbl0764.68054MR1170882
  18. [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. MR1230239
  19. [JJ92] Joseph JA JA, An Introduction to Parallel Algorithms, Addison Wesley, USA, 1992. Zbl0781.68009

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.