zbMATH — the first resource for mathematics

Linear time algorithms for NP-hard problems restricted to partial k- trees. (English) Zbl 0666.68067
We present and illustrate by a sequence of examples an algorithm paradigm for solving NP-hard problems on graphs resticted to partial graphs of k- trees and given with an embedding in a k-tree. Such algorithms, linear in the size of the graph but exponential or superexponential in k, exist for most NP-hard problems that have linear time algorithms for trees. The examples used are optimization problems involving independent sets, dominating sets, graph coloring, Hamiltonian circuits, network reliability and minimum vertex deletion forbidden subgraphs. The results generalize previous results for series-parallel graphs, bandwidth- constrained graphs, and non-serial dynamic programming.

68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Arnborg, S., Reduced state enumeration: another algorithm for reliability evaluation, IEEE trans. reliability, 27, 101-105, (1978) · Zbl 0436.60062
[2] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability: A survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018
[3] Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. algebraic discrete methods, 7, 305-314, (1986) · Zbl 0597.05027
[4] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebraic discrete methods, 8, 277-284, (1987) · Zbl 0611.05022
[5] Bern, M.W.; Lawler, E.L.; Wong, A.L., Linear time computation of optimal subgraphs of decomposable graphs, J. algorithms, 8, 216-235, (1987) · Zbl 0618.68058
[6] Bertele, U.; Brioschi, F., Nonserial dynamic programming, (1972), Academic Press New York · Zbl 0187.17801
[7] Corneil, D.G.; Keil, J.M., A dynamic programming approach to the dominating set problem on k-trees, SIAM J. algebraic discrete methods, 8, 535-543, (1987) · Zbl 0635.05040
[8] Corneil, D.G.; Lerchs, H.; Burlingham, L.Stewart, Complement reducible graphs, Discrete appl. math., 3, 163-174, (1981) · Zbl 0463.05057
[9] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[10] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. comput., 1, 180-187, (1972) · Zbl 0227.05116
[11] Johnson, D.S., The NP-completeness column: an ongoing guide, J algorithms, 4, (1984) · Zbl 0545.68032
[12] Lelann, G., (), 155-160
[13] Lingas, A., Subgraph isomorphism for easily separable graphs of bounded valence, ()
[14] Monien, B.; Sudborough, I.H., Bandwidth-constrained NP-complete problems, (), 207-217 · Zbl 0594.68042
[15] Robertson, N.; Seymour, P.D., Graph minors II: algorithmic aspects of freewidth, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[16] Rose, D., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[17] Rosenthal, A., Computing the reliability of a complex network, SIAM J. appl. math., 32, 384-393, (1977) · Zbl 0379.90048
[18] Rosenthal, A., Dynamic programming is optimal for nonserial optimization problems, SIAM J. comput., 11, 47-59, (1982) · Zbl 0479.90081
[19] Seese, D., Tree-partite graphs and the complexity of algorithms, (), Preprint, · Zbl 0574.68036
[20] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on seriesparallel graphs, J. ACM, 29, 623-641, (1982) · Zbl 0485.68055
[21] Wimer, T.V.; Hedetniemi, S.T.; Laskar, R., A methodology for constructing linear graph algorithms, (1985), DCS, Clemson University Clemson, SC · Zbl 0603.68040
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.