Skip to main content
SpringerLink
Log in

Applications of graph theory in computer systems

  • Published:
International Journal of Computer & Information Sciences Aims and scope Submit manuscript

Abstract

Many problem situations in computer systems can be analyzed using models based on directed graphs. The vertices of the graph represent states of the system and the directed arcs represent the transitions between these states. This paper is in two parts. The first introduces the concepts of directed graphs and their representations in computers and presents some basic problems and algorithms. The second part examines the application of graph theory to various areas of computer systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. F. Harary,Graph Theory (Addison-Wesley, 1969).

  2. C. Berge,The Theory of Graphs and their Applications, (Wiley, New York, 1962).

    Google Scholar 

  3. O. Ore,Graphs and Their Uses (Random House, New York, 1963).

    Google Scholar 

  4. R. G. Busacker and T. L. Saaty,Finite Graphs and Networks: An Introduction with Applications (McGraw-Hill, New York, 1965).

    Google Scholar 

  5. A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, 1974).

  6. P. D. Stigall and O. Tasar, “A review of directed graphs as applied to computers,”Computer 7(10):39–47 (1974).

    Google Scholar 

  7. S. Warshall, “A theorem on Boolean matrices,”J. ACM 9(1):11–12 (1962).

    Google Scholar 

  8. J. J. Baker, “A note on multiplying Boolean matrices,”Commun. ACM 5(2):102 (1962).

    Google Scholar 

  9. H. S. Warren, Jr., “A modification of Warshall's algorithm for the transitive closure of binary relations,”Commun. ACM 18(4):218–220 (1975).

    Google Scholar 

  10. L.E. Thorelli, “An algorithm for computing all paths in a graph,”BIT 6:347–349 (1966).

    Google Scholar 

  11. P. Purdom, “A transitive closure algorithm,”BIT 10(l):76–94 (1970).

    Google Scholar 

  12. I. Munro, “Efficient determination of the transitive closure of a directed graph,”Inf. Proc. Letters 1:56–58 (1971).

    Google Scholar 

  13. V. Strassen, “Gaussian elimination is not optimal,”Numerische Mathematik 13:354–356 (1969).

    Google Scholar 

  14. J. C. Tiernan, “An efficient search algorithm to find the elementary circuits of a graph,”Commun. ACM 13(12):722–726 (1970).

    Google Scholar 

  15. H. Weinblatt, “A new search algorithm for finding the simple cycles of a finite directed graph,”J. ACM 19(l):43–56 (1972).

    Google Scholar 

  16. R. E. Tarjan, “Enumeration of the elementary circuits of a directed graph,”SIAM J. Comp. 2(3; September):211–216 (1973).

    Google Scholar 

  17. C. V. Ramamoorthy, “Analysis of graphs by connectivity considerations,”J. ACM 13(2, April):211–222 (1966).

    Google Scholar 

  18. R. E. Tarjan, “Depth first search and linear graph algorithms,”SIAM J. Comp. 1(2; June):146–160 (1972).

    Google Scholar 

  19. C. P. Earnest, K. G. Balke, and J. Anderson, “Analysis of graphs by ordering of nodes,”J. ACM 19(1):23–42 (1972).

    Google Scholar 

  20. D. F. Martin and G. Estrin, “Models of computations and systems—evaluation of vertex probabilities in graph models of computations,”J. ACM 14(2; April):281–299 (1967).

    Google Scholar 

  21. D. F. Martin and G. Estrin, “Models of computations and systems—cyclic to acyclic graph transformations,”IEEE Trans, on Electronic Computers EC-16(February):70–79 (1967).

    Google Scholar 

  22. D. F. Martin and G. Estrin, “Experiments on models of computations and systems,”IEEE Trans, on Electronic Computers EC-16 (February):59–69 (1967).

    Google Scholar 

  23. D. F. Martin and G. Estrin, “Path length computations on graph models of computations,”IEEE Trans, on Computers C-18(June):530–536 (1969).

    Google Scholar 

  24. J. L. Baer, “A survey of some theoretical aspects of multiprocessing,”Computing Surveys 5(1; March):31–80 (1973).

    Google Scholar 

  25. J. L. Baer and G. Estrin, “Bounds for maximum parallelism in a bilogic graph model of computations,”IEEE Trans, on Computers C-18(11):1012–1014 (1969).

    Google Scholar 

  26. J. L. Baer, D. P. Bovet, and G. Estrin, “Legality and other properties of graph models of computations,”J. ACM 17(3; July):543–554 (1970).

    Google Scholar 

  27. J. L. Baer and G. Estrin, “A priori scheduling of bilogic graph models of computations,” inProject Planning by Network Analysis (North-Holland, 1969).

  28. J. L. Baer and E. C. Russell, “Preparation and evaluation of computer programs for parallel processing systems,” InParallel Processor Systems, Technologies and Applications, L. C. Hobbset al., Eds. (Spartan Books, New York 1970), pp. 375–415.

    Google Scholar 

  29. J. L. Baer, “Graph models of computation,” UCLA Dept. of Electrical Engineering Report 6846 (1968).

  30. R. M. Karp and R. A. Miller, “Properties of a model for parallel computations: determinacy, termination, queuing,”SIAM J. Appl. Math. 14(11):1390–1411 (1966).

    Google Scholar 

  31. Y. E. Chen and D. L. Epley, “Memory requirements in a multiprocessing environment,”J. ACM 19(1):57–69(1972).

    Google Scholar 

  32. R. T. Prosser, “Application of Boolean matrices to the analysis of flow diagrams,” inProc. Eeastern Joint Computer Conf. (1960), Vol. 16, pp. 133–138.

    Google Scholar 

  33. A. Schurmann, “The application of graphs to the analysis of distribution of loops in a program,”Information and Control 7(3):275–282 (1964).

    Google Scholar 

  34. A. T. Berztiss, “A note on segmentation of computer programs,”Information and Control 12(1):21–22 (1968).

    Google Scholar 

  35. C. V. Ramamoorthy, “The analytic design of a dynamic look ahead and program segmenting system for multiprogrammed computers,” inProc. 21st ACM Nat. Conf. (1966), pp. 229–239.

  36. T. C. Lowe, “Analysis of Boolean program models for timeshared, paged environments,”Commun. ACM 12(4):199–205 (1969).

    Google Scholar 

  37. T. C. Lowe, “Automatic segmentation of cyclic program structures based on connectivity and processor timing,”Commun. ACM 13(l):3–6 (1970).

    Google Scholar 

  38. K. Sattley and R. Millstein, “Comments on a paper by Lowe,”Commun. ACM 13(7):450–451 (1970).

    Google Scholar 

  39. E. W. Ver Hoef, “Automatic program segmentation based on Boolean connectivity,” inProc. AFIPS SJCC (1971), Vol.38, pp. 491–495.

    Google Scholar 

  40. J. L. Baer and R. Caughey, “Segmentation and optimization of programs from cyclic structure analysis,” inProc. AFIPS SJCC (1972), Vol.40, pp. 23–36.

    Google Scholar 

  41. B. W. Kernighan, “Optimal sequential partitions of graphs,”J. ACM 18(1):34–40 (1971).

    Google Scholar 

  42. C. Earnest, “Some topics in code optimization,”J. ACM 21(1):76–102 (1974).

    Google Scholar 

  43. J. Cocke and R. E. Miller, “Some analysis techniques for optimizing computer programs,” inProc. 2nd International Conference of System Sciences, Hawaii (1969).

  44. J. Cocke and J. T. Schwartz, “Programming languages and their compilers,” Preliminary Notes, Courant Inst, of Math. Sciences, New York University, New York (1970).

    Google Scholar 

  45. K. Kennedy, “A global flow analysis algorithm,”Int. J. Comp. Math. 3(1):5–15 (1971).

    Google Scholar 

  46. F. E. Allen, “Program optimization,” inAnnual Review in Automatic Programming (1969), Vol. 5.

  47. F. E. Alien, “Control flow analysis,” ACM SIGPLAN Notices5, 7 (July 1970), pp. 1–19.

    Google Scholar 

  48. F. E. Alien, “A basis for program optimization,” inProc. IFIP Congress 1971 (North-Holland).

  49. M. S. Hecht and J. D. Ullman, “Characterizations of reducible flow graphs,”J. ACM 21(3;July):367–375 (1974).

    Google Scholar 

  50. R. E. Tarjan, “Testing flow graph reducibility,” inProc. 5th Annual ACM Symp. on Theory of Computing, pp. 96–107.

  51. M. S. Hecht and J. D. Ullman, “Flow graph reducibility,”SIAM J. Comp. 1(2; June):188–202 (1972).

    Google Scholar 

  52. J. Cocke, “Global common subexpression elimination,” ACM SIGPLAN Notices, 5, 7 (July 1970), pp. 20–24.

    Google Scholar 

  53. J. D. Ullman, “Fast algorithms for the elimination of common subexpressions,”Acta Informatica 2(3; December):191–213 (1973).

    Google Scholar 

  54. D. H. R. Huxtable, “On writing an optimizing translator for ALGOL 60,” inIntroduction to System Programming, P. Wegner, ed. (Academic Press, 1964), pp. 137–155.

  55. E. N. Hawkins and D. H. R. Huxtable, “A Multi-pass translation scheme for ALGOL 60,” inAnnual Review in Automatic Programming (1962), Vol. 3, pp. 163–205.

    Google Scholar 

  56. E. S. Lowry and C. W. Medlock, “Object code optimization,”Commun. ACM 12(1): 13–22 (1969).

    Google Scholar 

  57. R. L. Kleir and C. V. Ramamoorthy, “Optimization strategies for microprograms,”Trans. IEEE on Computers C-20(7):783–794 (1971).

    Google Scholar 

  58. C. V. Ramamoorthy and R. L. Kleir, “A survey of techniques for optimizing microprograms,” inProc. 3rd Annual Workshop on Microprogramming, Buffalo, New York (1970).

  59. J. L. Szwarcfiter and P. E. Lauer, “Finding the elementary cycles of a directed graph inO(N + M) per cycle,” Tech. Rep. No. 60, Computing Lab. Univ. of Newcastle upon Tyne, England (May 1974).

    Google Scholar 

  60. C. V. Ramamoorthy and M. J. Gonzalez, “A survey of techniques for recognizing parallel processable streams in computer programs,” inProc. AFIPS FJCC (1969), Vol. 35, pp. 1–15.

    Google Scholar 

  61. C. V. Ramamoorthy and M. J. Gonzalez, “Recognition and representation of parallel processable streams in computer programs II (task/process parallelism),” inProc. 24th ACM Nat. Conf. (1969), pp. 387–397.

  62. E. C. Russell, “Automatic program analysis,” Ph.D. Thesis, Dept. of Elec. Eng., UCLA (1969).

  63. J. M. S. Simoes-Pereira, “On the Boolean matrix equationM′ = Ui=1 ∞ M′,”J. ACM 12(3; July):376–382 (1965).

    Google Scholar 

  64. L. W. Jackson and S. Dasgupta, “The identification of parallel micro-operations,”Inf. Proc. Letters 2:180–184 (1974).

    Google Scholar 

  65. R. M. Karp, “A note on the application of graph theory to digital computer programming,”Information and Control 3(6):179–190 (1960).

    Google Scholar 

  66. C. V. Ramamoorthy, “Discrete Markov analysis of computer programs,” inProc. 20th ACM Nat. Conf. (1965), pp. 386–392.

  67. J. D. Foley, “A Markovian model of the University of Michigan executive system,”Commun. ACM 10(9):584–589 (1967).

    Google Scholar 

  68. W. S. Bowie, “Towards a distributed architecture for OS/360,” Ph.D. Thesis, Dept. of Applied Analysis and Computer Science, Univ. of Waterloo, Waterloo, Ontario, Canada (1974).

    Google Scholar 

  69. W. S. Bowie, J. G. Linders, and W. Rushton, “A trace monitor program for OS/360,” inProc. Canadian Inf. Proc. Soc. Conf. Regina, Saskatchewan, Canada (June 1975).

  70. M. J. Gonzalez and C. V. Ramamoorthy, “Parallel task execution in a decentralized system,”IEEE Trans, on Computers C-21(12):1310–1322 (1972).

    Google Scholar 

  71. J. M. Feeley, “A computer performance monitor and Markov analysis for multiprocessor system evaluation,” inStatistical Computer Performance Evaluation, W. Frieberger, ed. (Academic Press, 1972), pp. 165–225.

  72. T. C. Lowe, “Analysis of an information system model with transfer penalties,”IEEE Trans, on Computers C-22(5):469–480 (1973).

    Google Scholar 

  73. R. C. Holt, “Some deadlock properties of computer systems,”Computing Surveys 4(3; September): 179–196 (1972).

    Google Scholar 

  74. J. E. Murphy, “Resource allocation with interlock detection in a multitask system,” inProc. AFIPS FJCC (1968), Vol.33, Part 2, pp. 1169–1176.

    Google Scholar 

  75. P. G. Hebalkar, “A graph model for analysis of deadlock prevention in systems with parallel computations,” inProc. IFIP Congress 1971, pp. 498–503.

  76. E. G. Coffman, M. J. Elphick, and A. Shoshani, “System deadlocks,”Computing Surveys 3(2; June):67–78 (1971).

    Google Scholar 

  77. K. M. Chandy and C. V. Ramamoorthy, “Rollback and recovery strategies for computer programs,”IEEE Trans, on Computers C-21(6):546–556 (1972).

    Google Scholar 

  78. W. Mayeda and C. V. Ramamoorthy, “Distinguishability criteria in oriented graphs and their application to computer diagnosis–I,”IEEE Trans, on Circuit Theory CT-16 (November):448–454 (1969).

    Google Scholar 

  79. C. V. Ramamoorthy, “A structural theory of machine diagnosis,” inProc. AFIPS SJCC (1967), Vol.30, pp. 743–756.

    Google Scholar 

  80. C. V. Ramamoorthy and L. C. Chang, “System modelling and testing procedures for microdiagnostics,”IEEE Trans, on Computers C-21(11):1169–1183 (1972).

    Google Scholar 

  81. C. V. Ramamoorthy and L. C. Chang, “System segmentation for the parallel diagnosis of computers,”IEEE Trans, on Computers C-20(3):261–270 (1971).

    Google Scholar 

Download references

Author information

Author notes

  1. William S. Bowie

    Present address: Department of Mathematics, University of Victoria, Victoria, British Columbia, Canada

Authors and Affiliations

  1. Department of Computing and Information Science, University of Guelph, Guelph, Ontario, Canada

    William S. Bowie

Authors
  1. William S. Bowie
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bowie, W.S. Applications of graph theory in computer systems. International Journal of Computer and Information Sciences 5, 9–31 (1976). https://doi.org/10.1007/BF00991069

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00991069

Key words

Search

Navigation