Practical algorithms on partial \(k\)-trees with an application to domination-like problems. (English) Zbl 1504.68183
Dehne, Frank (ed.) et al., Algorithms and data structures. 3rd workshop, WADS ’93. Montréal, Canada 11–13, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 709, 610-621 (1993).
Summary: Many NP-hard problems on graphs have polynomial, in fact usually linear, dynamic programming algorithms when restricted to partial \(k\)-trees (graphs of treewidth bounded by \(k\)), for fixed values of \(k\). We investigate the practicality of such algorithms, both in terms of their complexity and their derivation, and account for the dependency on the treewidth \(k\). We define a general procedure to derive the details of table updates in the dynamic programming solution algorithms. This procedure is based on a binary parse tree of the input graph. We give a formal description of vertex subset optimization problems in a class that includes several variants of domination, independence, efficiency and packing. We give algorithms for any problem in this class, which take a graph \(G\), integer \(k\) and a width \(k\) tree-decomposition of \(G\) as input, and solve the problem on \(G\) in \(O(n2^{4k})\) steps.
For the entire collection see [Zbl 0825.00122].
For the entire collection see [Zbl 0825.00122].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W40 | Analysis of algorithms |
References:
| [1] | K.Abrahamson and M.Fellows, Finite automata, bounded treewidth and wellquasiordering, to appear in Contemporary Mathematics (1992). |
| [2] | S.Arnborg, S.Hedetniemi and A.Proskurowski (editors) Algorithms on graphs with bounded treewidth, Special issue of Discrete Applied Mathematics. |
| [3] | S.Arnborg, J.Lagergren and D.Seese, Easy problems for tree-decomposable graphs, J. of Algorithms 12(1991) 308-340. · Zbl 0734.68073 |
| [4] | S. Arnborg and A. Proskurowski, Characterization and recognition of partial 3-trees, SIAM J. Alg. and Discr. Methods 7 (1986) 305-314. · Zbl 0597.05027 |
| [5] | S.Arnborg and A.Proskurowski, Linear time algorithms for NP-hard problems on graphs embedded in \(k\)-trees, Discr. Appl. Math. 23 (1989) 11-24. · Zbl 0666.68067 · doi:10.1016/0166-218X(89)90031-0 |
| [6] | M.W.Bern, E.L.Lawler and A.L.Wong, Linear-time computation of optimal subgraphs of decomposable graphs, J. of Algorithms 8(1987) 216-235. · Zbl 0618.68058 |
| [7] | H.L.Bodlaender, Dynamic programming on graphs with bounded treewidth, Proceedings ICALP 88, LNCS vol.317 (1988) 105-119. · Zbl 0649.68039 |
| [8] | H.L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, to appear in Proceedings STOC’93. |
| [9] | J.A.Bondy and U.S.R.Murty, Graph theory with applications, 1976. · Zbl 1226.05083 |
| [10] | R.B.Borie, R.G.Parker and C.A.Tovey, Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursive constructed graph families, Algorithmica, 7:555-582, 1992. · Zbl 0753.05062 · doi:10.1007/BF01758777 |
| [11] | E.J.Cockayne, B.L.Hartnell, S.T.Hedetniemi and R.Laskar, Perfect domination in graphs, manuscript (1992), to appear in Special issue of JCISS. |
| [12] | B.Courcelle, The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation, 85, (1990) 12-75. · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H |
| [13] | M.Garey and D.Johnson, Computers and Intractability, Freeman, San Fransisco, 1979. · Zbl 0411.68039 |
| [14] | D.Grinstead and P.Slater, A recurrence template for several parameters in seriesparallel graphs, manuscript (1992). |
| [15] | J. van Leeuwen, Graph Algorithms, in Handbook of Theoretical Computer Science vol. A, Elsevier, Amsterdam, (1990) pg. 550. · Zbl 0900.68258 |
| [16] | J.Matoušek and R.Thomas, Algorithms finding tree-decompositions of graphs, J. of Algorithms, 12 (1991) 1-22. · Zbl 0712.68077 |
| [17] | A.Proskurowski and M.Syslo, Efficient computations in tree-like graphs, in Computing Suppl 7, (1990) 1-15. · Zbl 0713.68034 |
| [18] | N. Robertson and P.D. Seymour, Graph minors II: algorithmic aspects of tree-width, J. of Algorithms 7 (1986) 309-322. · Zbl 0611.05017 |
| [19] | D.Sanders, On linear recognition of tree-width at most four, manuscript (1992). |
| [20] | K.Takamizawa, T.Nishizeki and N.Saito, Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM 29(1982) 623-641. · Zbl 0485.68055 · doi:10.1145/322326.322328 |
| [21] | J.A.Teile, Characterization of domination-type parameters in graphs, to appear in Proceedings of 24th SouthEastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium. |
| [22] | J.A.Telle, Complexity of domination-type problems in graphs, submitted BIT. |
| [23] | J.A.Telle and A.Proskurowski, Efficient sets in partial \(k\)-trees, to appear in Domination in graphs, Special volume of Discrete Applied Mathematics. |
| [24] | T.Wimer, Linear time algorithms on \(k\)-terminal graphs. Ph.D. thesis, Clemson University, South Carolina, (1988). |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
