Preview
Unable to display preview. Download preview PDF.
References
J. Barwise (ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam 1977.
B. Bollobás, Extremal Graph Theory, Academic Press, London 1978.
H.D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic, Undergraduate Texts in Mathematics, Springer-Verlag, New-York, 1984.
P. van Emde Boas, Dominoes are Forever, preprint 1983.
R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, in Complexity of Computation, (ed. R. Karp), SIAM — AMS Proc. 7, 1974, pp 27–41.
M.R. Garey, D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco 1978.
N. Immerman, Languages Which Capture Complexity Classes, acm-proceedings of the 15 annual acm symp. on the theory of computing, 1983, pp. 347–354.
M.O. Rabin, Decidability of second order theories and automata on infinite trees, Trans. Am. Math. Soc. 141, 1969, 1–35.
N. Robertson and P.D. Seymour, Graph minors I. Excluding a forest, J. Combin. Theory Ser. B 35, 1983, 39–61.
N. Robertson and P.D. Seymour, Graph Minors III. Planar Tree-Width, J. Combin. Theory Ser. B 36, 1984, 49–64.
P. Scheffler, personal communication.
D.G. Seese, Entscheidbarkeits-und Interpretierbarkeitsfragen monadischer Theorien zweiter Stufe gewisser Klassen von Graphen, Dissertation, Humboldt-Universität zu Berlin, 1976.
D.G. Seese, Ein Unentscheidbarkeitskriterium, Wiss. Z. der Humboldt-Univ. zu Berlin Math.-Nat. R. XXIV, 1975,6, 772–780.
D.G. Seese, Some Graph Theoretical Operations and Decidability, Math. Nachr. 87, 1979, 15–21.
K. Takamizawa, T. Nishizeki, N. Saito, Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs, J. of the Association for Computing Machinery, Vol. 29, No. 3, 1982, 623–641.
C. Thomassen, Infinite Graphs, in Selected Topics in Graph Theory 2, L.W. Beineke and R.J. Wilson (ed.), Acad. press, 1983, London, 129–160.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Seese, D. (1985). Tree-partite graphs and the complexity of algorithms. In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol 199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028825
Download citation
DOI: https://doi.org/10.1007/BFb0028825
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-15689-5
Online ISBN: 978-3-540-39636-9
eBook Packages: Springer Book Archive