A top down unification of minimum cost spanning tree algorithms

ABSTRACT

The problem of the design of communications networks has spawned the development of many of the algorithms currently used to solve the minimum cost spanning tree problem. We show that three minimum cost spanning tree algorithms, those by Kruskal, Prim, and Esau and Williams, can be derived from a single problem specification using “specification and transformation by parts,” a methodology for deriving families of algorithms. This approach is an alternative to the Kershenbaum and Chou unification of spanning tree algorithms. Whereas the Kershenbaum & Chou approach might be called bottom up, this is a top down approach which shows the original unity of the algorithms which emerges from the statement of the problem and also the essential differences. Besides pedagogical and aesthetic value, we maintain that an understanding of the algorithms from this perspective may be helpful in network design and modification.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: Chandy, K.M. and Russell, R.A. The design of multipoint linkages in a teleprocessing tree network. IEEE Trans. o_~n Computers, C-21, no. 10. (Oct. 1972).
• 3: Dewar, R.B.K., Merritt, S.M. and Sharir, M. Some modified algorithms for Dijkstra's longest upsequence problem. Acta Informatica 18. (1982).
• 4: J. T. Schwartz , R. B. Dewar , E. Schonberg , E. Dubinsky, Programming with sets; an introduction to SETL, Springer-Verlag New York, Inc., New York, NY, 1986
• 5: Dijkstra, E.W. A note on two problems in connection with graphs. Numerische Mathematik 1. (1959). pp 269-271.
• 6: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 7: Esau, L.R. and Williams, K.C. A model for approximating the optimal network. IBM Systems Journal, 5, no. 3 (1966).
• 8: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 9: Seymour E. Goodman , S. T. Hedetniemi, Introduction to the Design and Analysis of Algorithms, McGraw-Hill, Inc., New York, NY, 1977
• 10: David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 11: Kershenbaum, A. and Chou, W.S. Unified algorithm for designing multidrop teleprocessing networks. IEEE Trans. on Communications, COM-22, No. 11 (Nov. 1974).
• 12: Kruskal, A.G. On the shortest spanning subtree of a graph and the traveling salesman problems. Proc. American Mathematics Society, 7 (1956).
• 13: Henry Merriman Lewis , Robert B. Dewar, Extensions to setl to support problem specification and transformation of imperative programs, 1988
• 14: Susan Mary Merritt, The role of the high level specification in programming by transformation: specification and transformation by parts, 1982
• 15: Susan M. Merritt, An inverted taxonomy of sorting algorithms, Communications of the ACM, v.28 n.1, p.96-99, Jan. 1985 [doi>10.1145/2465.214925]
• 16: H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983 [doi>10.1145/356914.356917]
• 17: Prim, R.C. Shortest connection networks and some generalizations. Bell Systems Technical Journal~ 36. (Nov. 1957).
• 18: Mischa K. Schwartz, Computer Communications Network Design and Analysis, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 19: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design