×

zbMATH — the first resource for mathematics

Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. (English) Zbl 0753.05062
Summary: This paper describes a predicate calculus in which graph problems can be expressed. Any problem possessing such an expression can be solved in linear time on any recursively constructed graph, once its decomposition tree is known. Moreover, the linear-time algorithm can be generated automatically from the expression, because all our theorems are proved constructively. The calculus is founded upon a short list of particularly primitive predicates, which in turn are combined by fundamental logical operations. This framework is rich enough to include the vast majority of known linear-time solvable problems.
We have obtained these results independently of similar results by B. Courcelle, through utilization of the framework of W. M. Bern, E. L. Lawler and A. L. Wong [J. Algorithms 8, 216-235 (1987; Zbl 0618.68058)]. We believe our formalism is more practical for programmers who would implement the automatic generation machinery, and more readily understood by many theorists.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
03B10 Classical first-order logic
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
References:
[1] S. Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded decomposability,BIT,25 (1985), 2–23. · Zbl 0573.68018
[2] S. Arnborg, D. G. Corneil, and A. Proskurowski, Complexity of finding embeddings in ak-tree,SIAM Journal of Algebraic and Discrete Methods,8 (1987), 277–284. · Zbl 0611.05022
[3] A. Arnborg, J. Lagergren, and D. Seese, Problems easy for tree-decomposable graphs, (extended abstract)Proceedings of the 15th ICALP, Lecture Notes in Computer Science, Vol. 317. Springer-Verlag, Berlin (1988), pp. 38–51; to appear inJournal of Algorithms. · Zbl 0662.03030
[4] A. Arnborg and A. Proskurowski, Linear time algorithms forNP-hard problems on graphs embedded ink-trees, TRITA-NA-8404, Royal Institute of Technology, Sweden (1984). · Zbl 0527.68049
[5] M. Bauderon and B. Courcelle, Graph expressions and graph rewritings,Mathematical Systems Theory,20 (1987), 83–127. · Zbl 0641.68115
[6] M. W. Bern, E. L. Lawler, and A. L. Wong, Linear time computation of optimal subgraphs of decomposable graphs,Jornal of Algorithms,8 (1987), 216–235. · Zbl 0618.68058
[7] H. L. Bodlaender, Dynamic programming on graphs with bounded tree-width, Technical report, Laboratory for Computer Science,M.I.T. (1987); extended abstract inProceedings of ICALP (1988).
[8] H. L. Bodlaender, Planar graphs with bounded tree-width, RUU-CS-88-14, University of Utrecht (1988).
[9] H. L. Bodlaender,NC-algorithms for graphs with small treewidth,Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (J. van Leeuwen, ed.) (1988), Lecture Notes in Computer Science, Vol. 344, Springer-Verlag, Berlin (1988), pp. 1–10.
[10] H. L. Bodlaender, Polynomial algorithms for graph isomorphism and chromatic index on partialk-trees,Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (1988), pp. 223–232.
[11] B. Courcelle, Recognizability and second-order definability for sets of finitegraphs, Report 1-8634, Universite de Bordeaux (1987).
[12] B. Courcelle, An algebraic and logical theory of graphs, a survey, unpublished manuscript (1988). · Zbl 0679.68135
[13] M. R. Garey, R. L. Graham, D. S. Johnson, and D. E. Knuth, Complexity results for bandwidth minimization,SIAM Journal of Applied Mathematics,34 (1978), 477–495. · Zbl 0385.05048
[14] M. R. Garey and D. S. Johnson,Computers and Intractability, Freeman, San Francisco (1979).
[15] D. S. Johnson, TheNP-completeness column: an ongoing guide,Journal of Algorithms,6 (1985), 434–451. · Zbl 0608.68032
[16] S. Mahajan and J. G. Peters, Algorithms for regular properties in recursive graphs,Proceedings of the 25th Annual Allerton Conference on Communications, Control, and Computing (1987), pp. 14–23.
[17] R. L. Rardin and R. G. Parker, Tree subgraph isomorphism isNP-complete on series-parallel graphs, unpublished manuscript (1985).
[18] M. B. Richey, Combinatorial optimization on series-parallel graphs: algorithms and complexity, Ph.D. Thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology (1985).
[19] T. Schaefer, Complexity of some two-person perfect information games,Journal of Computer and System Sciences,16 (1978), 185–225. · Zbl 0383.90112
[20] P. Scheffler and D. Seese, A combinatorial and logical approach to linear-time computability, extended abstract (1986). · Zbl 1209.90362
[21] M. M. Syslo, The subgraph isomorphism problem for outerplanar graphs,Theoretical Computer Science,17 (1982), 91–97. · Zbl 0522.68061
[22] K. Takamizawa, T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs,Journal of the Association for Computing Machinery,29 (1982), 623–641. · Zbl 0485.68055
[23] T. V. Wimer, Linear algorithms onk-terminal graphs, Ph.D. Thesis, Report No. URI-030, Clemson University (1987). · Zbl 0669.05050
[24] T. V. Wimer, S. T. Hedetniemi, and R. Laskar, A methodology for constructing linear graph algorithms,Congressus Numerantium,50 (1985), 43–60. · 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.