The recognition of Series Parallel digraphs

ABSTRACT

We present an algorithm that recognizes the class of General Series Parallel digraphs and runs in time proportional to the size of its input. To perform this recognition task it is necessary to compute the transitive reduction and transitive closure of any General Series Parallel digraph. Our analysis is based on the relationship between General Series Parallel digraphs and a class of well known models of electrical networks.

REFERENCES

• 1: A. Adam, On graphs in which two vertices are distinguished, Acta Math. Acad. Sci. Hungary 12, 1961, 377-397.
• 2: A. V. Aho, M. R. Garey, and J. D. Ullman, The transitive reduction of a directed graph, SIAM J. Comput. 1, 2, 1972, 131-137.
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: R. J. Duffin, Topology of Series-Parallel Networks, Journal of Math Analysis and Applications 10, 1965, 303-318.
• 5: F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1971.
• 6: F. Harary, J. Krarup, and A Schwenk, Graphs suppressible to an edge, Canadian Math. Bull. 15, 2 1972, 201-204.
• 7: F. Harary and R. Norman, Some properties of line digraphs, Rendiconti del Circolo Matematico Palermo 9, 1960, 149-163.
• 8: J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2, 3, 1973, 135-158.
• 9: J. B. Klerlein, Characterizing line dipseudographs, Proceedings of the Sixth Conference on Combinatorics, Graph Theory, and Computing, 1975, 429-442.
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: E. L. Lawler, Sequencing Jobs to minimize total weighted completion time subject to precedence constraints, Annals of Discrete Math. 2, 1978, 75-90.
• 12: Philippe G. H. Lehot, An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph, Journal of the ACM (JACM), v.21 n.4, p.569-575, Oct. 1974 [doi>10.1145/321850.321853]
• 13: D. W. Matula, Subtree Isomorphism in O(n5/2), Annals of Discrete Math. 2, 1978.
• 14: C. L. Monma and J. B. Sidney, A general algorithm for optimal job sequencing with Series-Parallel costraints, Tech. Report No. 347, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, N.Y., July 1977.
• 15: J. Riordan and C. E. Shannon, The number of two terminal series parallel networks, Journal of Math. Physics 21, 1942, 83-93.
• 16: Barry K. Rosen, Tree-Manipulating Systems and Church-Rosser Theorems, Journal of the ACM (JACM), v.20 n.1, p.160-187, Jan. 1973 [doi>10.1145/321738.321750]
• 17: Ravi Sethi, Testing for the Church-Rosser Property, Journal of the ACM (JACM), v.21 n.4, p.671-679, Oct. 1974 [doi>10.1145/321850.321862]
• 18: J. B. Sidney, The two machine flow line problem with Series-Parallel precedence relations, Working paper 76-19, Faculty of Management Sciences, University of Ottawa, November 1976.
• 19: J. Valdes, Parsing Flowcharts and Series-Parallel Graphs, Technical Report STAN-CS-78-682, Computer Science Department, Stanford University, Stanford, Ca., 1978.
• 20: T. R. S. Walsh, Counting labelled three-connected and homeomorphically irreducible two-connected graphs, (Manuscript), 1978.
• 21: L. Weinberg, Linear Graphs: theorems, algorithms, and applications, in Aspects of Network and System Theory, R. E. Kalman and N. DeClaris (eds.), Holt, Rinehart, and Winston, N.Y., 1971.

INDEX TERMS

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

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

General Terms:
Algorithms, Theory