A recurrence template for several parameters in series-parallel graphs. (English) Zbl 0812.68099

Summary: We present a single set of recurrence parameters and a single set of recurrence relations which can be used to provide a linear algorithm for evaluating a wide class of graph theoretic parameters for series-parallel graphs. The set of recurrences presented here is no larger than has been necessary in solving any one of the parameters. Problems that can be solved using our template of recurrence relations include those involving the concepts of domination, packing, redundance, and independence.


68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory
Full Text: DOI


[1] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, TRITA-NA-8404 (1984), The Royal Institute of Technology
[2] Bange, D. W.; Barkauskas, A. E.; Slater, P. J., Disjoint dominating sets in trees, Sandia Laboratories Report (1978), SAND 78-1087J
[3] Bange, D. W.; Barkauskas, A. E.; Slater, P. J., Efficient dominating sets in graphs, (Applications of Discrete Math. (1988), SIAM: SIAM Philadelphia, PA), 189-199 · Zbl 0664.05027
[4] Bange, D. W.; Barkauskas, A. E.; Host, L.; Slater, P. J., Efficient near-domination of grid graphs, Congr. Numer., 58, 83-92 (1987)
[5] Bern, M. W.; Lawler, E. L.; Wong, A. L., Why certain subgraph computations require only linear time, Proceedings of 26th Symposium on Foundations of Computer Science (October, 1985)
[6] Beyer, T.; Proskurowski, A.; Hedetniemi, S.; Mitchell, S., Independent domination in trees, (Proceedings of 8th S.E. Conference on Combinatorics, Graph Theory, and Computing (1977), Utilitas Math: Utilitas Math Winnipeg), 231-238 · Zbl 0417.05020
[7] Borie, R. B.; Parker, R. G.; Tovey, C. A., Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, 555-581 (1992) · Zbl 0753.05062
[9] Courcelle, B., The monadic second order logic of graphs I: recognizable sets of finite graphs, Inform. and Comput., 85, 1, 12-75 (1990) · Zbl 0722.03008
[10] Grinstead, D. L.; Slater, P. J., Fractional domination and fractional packing in graphs, Congr. Numer., 71, 153-172 (1990) · Zbl 0691.05043
[12] Hare, E.; Hedetniemi, S.; Laskar, R.; Peters, K.; Wimer, T., Linear Time Computability of Combinatorial Problems on Generalized Series-Parallel Graphs, (Discrete algorithms and Complexity (1987), Academic Press: Academic Press New York), 437-457 · Zbl 0643.68093
[14] Hedetniemi, S. T.; Laskar, R., Recent results and open problems in domination theory, (Applications of Discrete Math. (1988), SIAM: SIAM Philadelphia, PA), 205-218 · Zbl 0664.05026
[15] Hedetniemi, S. T.; Wimer, T. V., \(k\)-Terminal recursive families of graphs, Congr. Numer., 63, 161-176 (1988) · Zbl 0673.05081
[16] Hochbaum, D. S.; Schmoys, D. B., A best possible heuristic for the \(k\)-center problem, Math. Oper. Res., 10, 180-184 (1985) · Zbl 0565.90015
[18] Kikuno, T.; Yoshida, N.; Kakuda, Y., A linear algorithm for the domination number of a series-parallel graph, Discrete Appl. Math., 5, 299-311 (1983) · Zbl 0507.05060
[19] Meir, A.; Moon, J. W., Relations between packing and covering numbers of a tree, Pacific J. Math., 61, 225-233 (1975) · Zbl 0315.05102
[20] Pfaff, J.; Laskar, R.; Hedetniemi, S. T., Linear algorithms for independent domination and total domination in series-parallel graphs, Congr. Numer., 45, 71-82 (1985)
[21] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 623-641 (1982) · Zbl 0485.68055
[22] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series-parallel digraphs, SIAM J. Comput., 11, 2, 298-313 (1982) · Zbl 0478.68065
[23] Wimer, T. V.; Hedetniemi, S. T.; Laskar, R., A methodology for constructing linear graph algorithms, Congr. Numer., 50, 43-60 (1985) · Zbl 0603.68040
[24] Wimer, T. V., Linear algorithms on \(k\)-terminal graphs, Ph.D. Dissertation (1987), Computer Science Department, Clemson University · Zbl 0669.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.