{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:39:54Z","timestamp":1767339594664,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651956"},{"type":"electronic","value":"9783540494942"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/10692760_1","type":"book-chapter","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T16:35:37Z","timestamp":1277915737000},"page":"1-16","source":"Crossref","is-referenced-by-count":28,"title":["Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width"],"prefix":"10.1007","author":[{"given":"B.","family":"Courcelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. A.","family":"Makowsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U.","family":"Rotics","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree decomposable graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Buer, H., M\u00f6hring, R.H.: A fast algorithm for the decomposition of graphs and posets. Math. Oper. Res.\u00a08, 170\u2013184 (1983)","DOI":"10.1287\/moor.8.2.170"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-60618-1_63","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"L. Babel","year":"1995","unstructured":"Babel, L., Olariu, S.: On the isomorphism of graphs with few P 4s. In: Nagl, M. (ed.) WG 1995. LNCS, vol.\u00a01017, pp. 24\u201336. Springer, Heidelberg (1995)"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/10692760_27","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"L. Babel","year":"1998","unstructured":"Babel, L., Olariu, S.: Domination and steiner tree problems on graphs with few P4\u2019s. In: Hromkovi\u010d, J., S\u00fdkora, O. (eds.) WG 1998. LNCS, vol.\u00a01517, pp. 337\u2013350. Springer, Heidelberg (1998)"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. System Sci.\u00a046, 218\u2013270 (1993)","journal-title":"J. Comput. System Sci."},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. LNCS, vol.\u00a0787, pp. 68\u201384 (1994)","DOI":"10.1007\/BFb0017474"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science \u00a0109, 49\u201382 (1993)","DOI":"10.1016\/0304-3975(93)90064-Z"},{"key":"1_CR8","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs (submitted for publication), http:\/\/dept-info.labri.u-bordeaux.fr\/courcell\/ActSci.html"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs i: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0304-3975(91)90387-H","volume":"80","author":"B. Courcelle","year":"1991","unstructured":"Courcelle, B.: The monadic second-order logic of graphs V: On closing the gap between definability and recognizability. Theoret. Comput. Sci.\u00a080, 153\u2013202 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","volume":"54","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B.: The monadic second-order logic of graphs VI: On several representations of graphs by relational structures. Disc. Appl. Math.\u00a054, 117\u2013149 (1994)","journal-title":"Disc. Appl. Math."},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0168-0072(95)94698-V","volume":"72","author":"B. Courcelle","year":"1995","unstructured":"Courcelle, B.: The monadic second-order logic of graphs VIII: Orientations. Annals Pure Applied Logic\u00a072, 103\u2013143 (1995)","journal-title":"Annals Pure Applied Logic"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0304-3975(95)00083-6","volume":"160","author":"B. Courcelle","year":"1996","unstructured":"Courcelle, B.: The monadic second-order logic of graphs X: Linear orders. Theoret. Comput. Sci.\u00a0160, 87\u2013143 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR14","series-title":"Foundations","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1142\/9789812384720_0005","volume-title":"Handbook of graph grammars and computing by graph transformations","author":"B. Courcelle","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Rozenberg, G. (ed.) Handbook of graph grammars and computing by graph transformations. Foundations, Ch. 5, vol.\u00a01, pp. 313\u2013400. World Scientific, Singapore (1997)"},{"key":"1_CR15","volume-title":"Finite Model Theory. Perspectives in Mathematical Logic","author":"H.D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic. Springer, Heidelberg (1995)"},{"key":"1_CR16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"Ehrenfeucht, A.: An application of games to the completeness problem for formalized theories. Fundamenta Mathematicae\u00a049, 129\u2013141 (1961)","journal-title":"Fundamenta Mathematicae"},{"key":"1_CR17","first-page":"27","volume":"7","author":"R. Fagin","year":"1974","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial time recognizable sets. American Math. Society Proc.\u00a07, 27\u201341 (1974)","journal-title":"American Math. Society Proc."},{"key":"1_CR18","unstructured":"Feferman, S.: Some recent work of Ehrenfeucht and Fra\u00efss\u00e9. In: Proceedings of the Summer Institute of Symbolic Logic, Ithaca, pp. 201\u2013209 (1957)"},{"key":"1_CR19","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4064\/fm-47-1-57-103","volume":"47","author":"S. Feferman","year":"1959","unstructured":"Feferman, S., Vaught, R.: The first order properties of algebraic systems. Fundamenta Mathematicae\u00a047, 57\u2013103 (1959)","journal-title":"Fundamenta Mathematicae"},{"key":"1_CR20","series-title":"Mathematical Series","volume-title":"Computers and Intractability","author":"M.G. Garey","year":"1979","unstructured":"Garey, M.G., Johnson, D.S.: Computers and Intractability. Mathematical Series. W.H. Freeman and Company, New York (1979)"},{"key":"1_CR21","doi-asserted-by":"crossref","first-page":"17","DOI":"10.46298\/dmtcs.232","volume":"1","author":"V. Giakoumakis","year":"1997","unstructured":"Giakoumakis, V., Roussel, F., Thuillier, H.: On P4-tidy graphs. Discrete Mathematics and Theoretical Computer Science\u00a01, 17\u201341 (1997)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"481","DOI":"10.2307\/2273287","volume":"44","author":"Y. Gurevich","year":"1979","unstructured":"Gurevich, Y.: Modest theory of short chains. I. Journal of Symbolic Logic\u00a044, 481\u2013490 (1979)","journal-title":"I. Journal of Symbolic Logic"},{"key":"1_CR23","volume-title":"Model-Theoretic Logics, Perspectives in Mathematical Logic, Chap. 14","author":"Y. Gurevich","year":"1985","unstructured":"Gurevich, Y.: Monadic second order theories. In: Model-Theoretic Logics, Perspectives in Mathematical Logic, Ch. 14. Springer, Heidelberg (1985)"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0304-3975(96)00220-4","volume":"180","author":"V. Giakoumakis","year":"1997","unstructured":"Giakoumakis, V., Vanherpe, J.: On extended P 4-reducible and extended P4-sparse graphs. Theoret. Comput. Sci.\u00a0180, 269\u2013286 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR25","unstructured":"Ho\u00e0ng, C.: Doctoral thesis. McGill University, Montreal (1985)"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/sapm198981179","volume":"81","author":"B. Jamison","year":"1989","unstructured":"Jamison, B., Olariu, S.: P4-reducible graphs a class of tree representable graphs. Studies Appl. Math.\u00a081, 79\u201387 (1989)","journal-title":"Studies Appl. Math."},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1137\/0221027","volume":"21","author":"B. Jamison","year":"1992","unstructured":"Jamison, B., Olariu, S.: A linear-time recognition algorithm for P4-sparse graphs. SIAM J. Comput.\u00a021, 381\u2013406 (1992)","journal-title":"SIAM J. Comput."},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(92)90036-A","volume":"35","author":"B. Jamison","year":"1992","unstructured":"Jamison, B., Olariu, S.: A unique tree representation for P4-sparse graphs. Discrete Appl. Math.\u00a035, 115\u2013129 (1992)","journal-title":"Discrete Appl. Math."},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(95)00016-P","volume":"145","author":"B. Jamison","year":"1995","unstructured":"Jamison, B., Olariu, S.: A linear-time algorithm to recognize P4-reducible graphs. Theoret. Comput. Sci.\u00a0145, 329\u2013344 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0166-218X(94)00012-3","volume":"61","author":"B. Jamison","year":"1995","unstructured":"Jamison, B., Olariu, S.: Linear-time optimization algorithms for P4-sparse graphs. Discrete Appl. Math.\u00a061, 155\u2013175 (1995)","journal-title":"Discrete Appl. Math."},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"L\u00e4uchli, H.: A decision procedure for the weak second order theory of linear order. In: Logic Colloquium 1966, pp. 189\u2013197. North Holland, Amsterdam (1968)","DOI":"10.1016\/S0049-237X(08)70525-1"},{"key":"1_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/3-540-56992-8_19","volume-title":"Logical definability of NP-optimization problems with monadic auxiliary predicates","author":"C. Lautemann","year":"1993","unstructured":"Lautemann, C.: CSL 1992. LNCS, vol.\u00a0702, pp. 327\u2013339. Springer, Heidelberg (1993)"},{"key":"1_CR33","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison Wesley, Reading (1994)"},{"key":"1_CR34","unstructured":"Rotics, U.: Efficient Algorithms for Generally Intractable Graph Problems Restricted to Specific Classes of Graphs. PhD thesis, Technion- Israel Institute of Technology (1998)"},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"Shelah, S.: The monadic theory of order. Annals of Mathematics\u00a0102, 379\u2013419 (1975)","journal-title":"Annals of Mathematics"},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0166-218X(92)90180-I","volume":"39","author":"J. Spinrad","year":"1992","unstructured":"Spinrad, J.: P4 -trees and substitution decomposition. Discrete Appl. Math.\u00a039, 263\u2013291 (1992)","journal-title":"Discrete Appl. Math."},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E. Wanke","year":"1994","unstructured":"Wanke, E.: k-NLC graphs and polynomial algorithms. Discrete Appl. Math.\u00a054, 251\u2013266 (1994)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10692760_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T12:05:58Z","timestamp":1635595558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10692760_1"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651956","9783540494942"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/10692760_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}