×

zbMATH — the first resource for mathematics

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.

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[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, (), 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, (), 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
[8] D.G. Corneil and J.M. Keil, The complexity of the dominating set problem on k-trees, Ann. Discrete Math., to appear. · Zbl 0635.05040
[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
[11] D.L. Grinstead, Further applications of a Recurrence Template for Series—Parallel Graphs, in preparation. · Zbl 0812.68099
[12] Hare, E.; Hedetniemi, S.; Laskar, R.; Peters, K.; Wimer, T., Linear time computability of combinatorial problems on generalized series – parallel graphs, (), 437-457 · Zbl 0643.68093
[13] S.M. Hedetniemi, S.T. Hedetniemi and T.V. Wimer, Linear time resource allocation algorithms for trees, manuscript. · Zbl 0603.68040
[14] Hedetniemi, S.T.; Laskar, R., Recent results and open problems in domination theory, (), 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
[17] T.W. Johnson and P.J. Slater, Maximum independent, minimally redundant sets in series – parallel graphs, submitted. · Zbl 0794.05124
[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.