Flow network reduction for unique topological ordering

ABSTRACT

This paper describes a more restrictive definition of cutsets as they are found useful in solving certain problems and presents a reduction method to reduce a flow network (an acyclic weighted digraph) with multiple topological orderings of vertices so that (1) the resulting reduced network has only one topological ordering and (2) the original network and the reduced network have the same maximal cutset. The motivation for such a reduction method is that if a network has only one topological ordering then the maximal cutset can be found in a linear time (linear in terms of the number of arcs).

REFERENCES

• 1: Koh, Hikyoo, "Restrictive Cutsets in a Flow Network and t h e i r Applications," submitted to Fifth International Conference on Data Engineering.
• 2: Koh, Hikyoo and Chuang, Henry, "Finding mal Set of Base Paths of a Program," tional Journal of Computer and Information Sciences, December 1979, pp. 473-488.
• 3: Ellis Horowitz , Sartaj Sahni, Fundamentals of data structures in PASCAL, Computer Science Press, Inc., New York, NY, 1984
• 4: Hikyoo Koh, Analysis of program structure for test input generation in a successive testing environment., 1978
• 5: Ford, L. R. and Fulkerson, D. R., Flows works, Princeton University, 1962.
• 6: Papadimitriou, C. H. and Steiglitz, national Optimization, Prentice-Hall, 91-97, 117-124.
• 7: Koh, Hikyoo, "Partitioning Program Digraph Intervals - A Systematic Method for ting Execution Sequences," ACM Computer Conference, 1982.
• 8: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

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

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

General Terms:
Algorithms, Design