×

zbMATH — the first resource for mathematics

Linear-time computability of combinatorial problems on generalized- series-parallel graphs. (English) Zbl 0643.68093
Discrete algorithms and complexity, Proc. Jap.-US Joint Semin., Kyoto/Jap. 1986, Perspect. Comput. 15, 437-457 (1987).
Summary: [For the entire collection see Zbl 0636.00011.]
This paper extends in several ways the notable work of K. Takamizawa, T. Nishizeki and N. Saito [J. Assoc. Comput. Mach. 29, 623-641 (1982; Zbl 0485.68055)], which in turn was inspired by that of T. Watanabe, T. Ae and A. Nakamura [“On the node cover problem of planar graphs”, Proc. 1979 Int. Symp. Convexity Syst., Tokio/Jap., 78-81 (1979)]. We illustrate an emerging theory/methodology for constructing linear-time graph algorithms by providing such algorithms for finding the maximum-cut and the maximum cardinality of a minimal dominating set for a generalized series-parallel graph.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity