Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey. (English) Zbl 0573.68018

Arnborg, Stefan

BIT 25, 2-23 (1985).

The paper is concerned with polynomial-time algorithms for restricted versions of some NP-hard problems on graphs. It surveys the use of table- based reduction methods for solving combinatorial problems defined on graphs and hypergraphs of bounded dimension and for problems defined on clique separable graphs and complement decomposable graphs. Some examples illustrate the use of the methods described.

Reviewer: J.Błażewicz

MSC:

68Q25	Analysis of algorithms and problem complexity
68R10	Graph theory (including graph drawing) in computer science
68-02	Research exposition (monographs, survey articles) pertaining to computer science

Keywords:

polynomial-time algorithms; NP-hard problems on graphs; table-based reduction methods

References:

[1]	A. V. Aho, J. E. Hopcroft and J. D. Ullman,Design and Analysis of Computer Algorithms, Reading, Mass. Addison-Wesley, 1974. · Zbl 0326.68005
[2]	S. Arnborg,Reduced state enumeration – another algorithm for reliability evaluation, IEEE Trans. Reliability R-27 (1978), 101–105. · Zbl 0436.60062
[3]	S. Arnborg,On the complexity of multivariable query evaluation, FOA Rapport C 20292-D8, National Defence Research Institute, Stockholm, Sweden (1979).
[4]	S. Arnborg, D. G. Corneil and A. Proskurowski,Complexity of finding embeddings in a k-tree, TRITA-NA 8407, Royal Institute of Technology, Sweden (1984). · Zbl 0544.68047
[5]	S. Arnborg and A. Proskurowski,Characterization and recognition of partial k-trees, TRITA-NA 8402, Royal Institute of Technology, Sweden (1984). · Zbl 0527.90037
[6]	S. Arnborg and A. Proskurowski,Linear time algorithms for NP-hard problems on graphs embedded in k-trees, TRITA-NA-8404, The Royal Institute of Technology (1984). · Zbl 0527.68049
[7]	B. Aspvall,Efficient algorithms for certain satisfiability and linear programming problems, PhD Thesis, STAN-CS-80-822, Stanford University, 1980.
[8]	L. W. Beineke and R. E. Pippert,Properties and characterizations of k-trees, Mathematika 18 (1971), 141–151. · Zbl 0221.05057
[9]	U. Bertele and F. Brioschi,Nonserial Dynamic Programming, Academic Press, New York, 1972. · Zbl 0244.49007
[10]	C. J. Colbourn and A. Proskurowski,Concurrent transmissions in broadcast networks, in Proc. 11th Int’l Coll. on Automata, Languages, and Programming, Antwerp, Springer Verlag, Berlin (1984), 128–136.
[11]	D. G. Cornell and J. M. Keil,A dynamic programming approach to the dominating set problem on k-trees, Dept. of Computer Science, University of Toronto, Technical report (1983).
[12]	D. G. Corneil, H. Lerchs and L. Stewart Burlingham,Complement reducible graphs, Discrete Appl. Math. 3 (1981), 163–174. · Zbl 0463.05057
[13]	M. Davis and H. Putnam,A computing procedure for quantification theory, J. ACM 7 (1960), 201–215. · Zbl 0212.34203
[14]	R. J. Duffin,Topology of series-parallel networks, J. Math. Anal. Appl. 10 (1965), 303–318. · Zbl 0128.37002
[15]	E. C. Freuder,Synthesizing constraint expressions, C. ACM 21 (1978), 958–966. · Zbl 0386.68065
[16]	M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth,Complexity results for bandwidth minimization, SIAM J. Appl. Math. 34 (1978), 835–859. · Zbl 0385.05048
[17]	M. R. Garey and D. S. Johnson,Computers and Intractability, W. H. Freeman and Company, San Francisco (1979).
[18]	F. Gavril,Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of chordal graph, SIAM J. Comput. 1 (1972), 180–187. · Zbl 0227.05116
[19]	G. Huet and D. Oppen,Equations and rewrite rules: a survey, in Formal Languages: Perspective and Open Problems (R. Book, Ed.), Academic Press, New York, 1980.
[20]	D. S. Johnson,The NP-Completeness column: an ongoing guide, J. of Algorithms 1–4 (1981–4). · Zbl 0494.68047
[21]	S. Kirkpatrick, C.D. Gelatt, Jr. and M. P. Vecchi,Optimization by simulated annealing, SCIENCE 220 (1983), 671–680. · Zbl 1225.90162
[22]	D. Rose,Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32, (1970), 597–609. · Zbl 0216.02602
[23]	D. Rose,On simple characterizations of k-trees, Discrete Math. 7 (1974), 317–322. · Zbl 0285.05128
[24]	A. Rosenthal,Computing the reliability of a complex network, SIAM J. Appl. Math. 32 (1977) 384–393. · Zbl 0379.90048
[25]	A. Rosenthal,Dynamic programming is optimal for nonserial optimization problems, SIAM J. Comput. 11 (1982), 47–59. · Zbl 0479.90081
[26]	A. Rosenthal,Series-parallel reduction for difficult measures of network reliability, NETWORKS 11 (1981), 323–334.
[27]	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
[28]	R. E. Tarjan,Decomposition by clique separators, Discrete Math., to appear. · Zbl 0572.05039
[29]	J. A. Wald and C. J. Colbourn,Steiner trees, partial 2-trees, and minimum IFI networks, Networks 13 (1983), 159–167. · Zbl 0529.68036
[30]	D. L. Walz,Generating semantic descriptions from drawings of scenes with shadows. AI-TR-271, A.I. Lab, M.I.T., Cambridge, Mass., 1972.
[31]	S. H. Whitesides,An algorithm for finding clique cutsets, Inf. Proc. Letters 12 (1981), 31–32. · Zbl 0454.68078
[32]	M. Yannakakis,Computing the minimum fill-in is NP-complete, SIAM J. Alg. and Discr. Methods 2 (1981), 77–79. · Zbl 0496.68033
[33]	M. Yannakakis,A polynomial algorithm for the MIN CUT LINEAR ARRANGEMENT of Trees, Proc. 24th Annual Symp. on Foundations of Computer Science, IEEE, 1983, 274–281.