{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T15:49:27Z","timestamp":1762271367151},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,8,27]],"date-time":"2009-08-27T00:00:00Z","timestamp":1251331200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,1]]},"DOI":"10.1007\/s10878-009-9260-7","type":"journal-article","created":{"date-parts":[[2009,8,26]],"date-time":"2009-08-26T18:19:51Z","timestamp":1251310791000},"page":"19-46","source":"Crossref","is-referenced-by-count":6,"title":["Compact labelings for efficient first-order model-checking"],"prefix":"10.1007","volume":"21","author":[{"given":"Bruno","family":"Courcelle","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[]},{"given":"Mamadou Moustapha","family":"Kant\u00e9","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,27]]},"reference":[{"issue":"2","key":"9260_CR1","doi-asserted-by":"crossref","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 (1991) Easy problems for tree-decomposable graphs. J Algorithms 12(2):308\u2013340","journal-title":"J Algorithms"},{"key":"9260_CR2","unstructured":"Bagan G (2009) Algorithmes et complexit\u00e9 des probl\u00e8mes d\u2019\u00e9num\u00e9ration pour l\u2019\u00e9valuation de requ\u00eates logiques. PhD Thesis, Universit\u00e9 de Caen\/Basse Normandie, Caen"},{"issue":"6","key":"9260_CR3","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1016\/j.ic.2005.11.006","volume":"204","author":"A Blumensath","year":"2006","unstructured":"Blumensath A, Courcelle B (2006) Recognizability, hypergraph operations and logical types. Inf Comput 204(6):853\u2013919","journal-title":"Inf Comput"},{"issue":"6","key":"9260_CR4","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender HL (1996) A linear-time algorithm for finding tree-decompositions of small tree-width. SIAM J Comput 25(6):1305\u20131317","journal-title":"SIAM J Comput"},{"key":"9260_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-540-72951-8_3","volume-title":"Structural information and communication complexity (SIROCCO)","author":"HL Bodlaender","year":"2007","unstructured":"Bodlaender HL (2007) Tree-width: structure and algorithms. In: Principe G, Zaks S (eds) Structural information and communication complexity (SIROCCO). LNCS, vol 4474. Springer, Berlin, pp 11\u201325"},{"issue":"1\u20133","key":"9260_CR6","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle B, Olariu S (2000) Upper bounds to the clique-width of graphs. Discrete Appl Math 101(1\u20133):77\u2013114","journal-title":"Discrete Appl Math"},{"key":"9260_CR7","doi-asserted-by":"crossref","unstructured":"Courcelle B, Twigg A (2009) Constraint-path labelings on graphs of bounded clique-width. To appear in Theory Comput Syst. A full version is available at doi: 10.1007\/s00224-009-9211-9","DOI":"10.1007\/s00224-009-9211-9"},{"issue":"1","key":"9260_CR8","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0166-218X(02)00421-3","volume":"131","author":"B Courcelle","year":"2003","unstructured":"Courcelle B, Vanicat R (2003) Query efficient implementation of graphs of bounded clique-width. Discrete Appl Math 131(1):129\u2013150","journal-title":"Discrete Appl Math"},{"issue":"2","key":"9260_CR9","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle B, Makowsky JA, Rotics U (2000) Linear-time solvable optimization problems on graphs of bounded clique-width. Theory Comput Syst 33(2):125\u2013150","journal-title":"Theory Comput Syst"},{"key":"9260_CR10","unstructured":"Courcelle B, Gavoille C, Kant\u00e9 MM, Twigg A (2008) Optimal labeling for connectivity checking in planar networks with obstacles. Manuscript, 2008. An extended abstract about 3-connected planar graphs is published in Electronic Notes in Discrete Mathematics 31:151\u2013155 (2008). The proceedings of the first Conference Topological and Geometric Graph Theory (TGGT), Paris, 2008"},{"key":"9260_CR11","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1109\/LICS.2007.31","volume-title":"22nd IEEE symposium on logic in computer science (LICS)","author":"A Dawar","year":"2007","unstructured":"Dawar A, Grohe M, Kreutzer S (2007) Locally excluding a minor. In: 22nd IEEE symposium on logic in computer science (LICS). IEEE Computer Society, New York, pp 270\u2013279"},{"key":"9260_CR12","volume-title":"Graph theory","author":"R Diestel","year":"2005","unstructured":"Diestel R (2005) Graph theory, 3rd edn. Springer, Berlin","edition":"3"},{"key":"9260_CR13","doi-asserted-by":"crossref","unstructured":"Durand A, Grandjean E (2007) First-order queries on structures of bounded degree are computable with constant delay. ACM Trans Comput Log 8(4)","DOI":"10.1145\/1276920.1276923"},{"issue":"4","key":"9260_CR14","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0020-0190(94)90121-X","volume":"51","author":"D Eppstein","year":"1994","unstructured":"Eppstein D (1994) Arboricity and bipartite subgraph listing algorithms. Inf Process Lett 51(4):207\u2013211","journal-title":"Inf Process Lett"},{"issue":"4","key":"9260_CR15","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E Fisher","year":"2008","unstructured":"Fisher E, Makowsky JA, Ravve EV (2008) Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Appl Math 156(4):511\u2013529","journal-title":"Discrete Appl Math"},{"issue":"1","key":"9260_CR16","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/s00224-003-1111-9","volume":"37","author":"M Frick","year":"2004","unstructured":"Frick M (2004) Generalized model-checking over locally tree-decomposable classes. Theory Comput Syst 37(1):157\u2013191","journal-title":"Theory Comput Syst"},{"issue":"1","key":"9260_CR17","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M Frick","year":"2001","unstructured":"Frick M, Grohe M (2001) Deciding first-order properties of locally tree-decomposable structures. J ACM 48(1):1184\u20131206","journal-title":"J ACM"},{"key":"9260_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0049-237X(08)71879-2","volume-title":"Proceedings of the herbrand symposium, logic colloquium\u201981","author":"H Gaifman","year":"1982","unstructured":"Gaifman H (1982) On local and non-local properties. In: Stern J (ed) Proceedings of the herbrand symposium, logic colloquium\u201981. North-Holland, Amsterdam, pp 105\u2013135"},{"issue":"2\u20133","key":"9260_CR19","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C Gavoille","year":"2003","unstructured":"Gavoille C, Peleg D, (2003) Compact and localized distributed data structures. Distrib Comput 16(2\u20133):111\u2013120","journal-title":"Distrib Comput"},{"key":"9260_CR20","first-page":"357","volume-title":"Logic, automata, history and perspectives","author":"M Grohe","year":"2007","unstructured":"Grohe M (2007) Logic, graphs and algorithms. In: Flum J, Gr\u00e4del E, Wilke T (eds) Logic, automata, history and perspectives. Amsterdam University Press, Amsterdam, pp 357\u2013422"},{"issue":"22","key":"9260_CR21","doi-asserted-by":"crossref","first-page":"2734","DOI":"10.1016\/j.disc.2007.01.020","volume":"307","author":"F Gurski","year":"2007","unstructured":"Gurski F, Wanke E (2007) Line graphs of bounded clique-width. Discrete Math 307(22):2734\u20132754","journal-title":"Discrete Math"},{"issue":"3","key":"9260_CR22","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd P, Oum S (2008) Finding branch-decompositions and rank-decompositions. SIAM J Comput 38(3):1012\u20131032","journal-title":"SIAM J Comput"},{"key":"9260_CR23","doi-asserted-by":"crossref","unstructured":"Kami\u0144ski M, Lozin V, Milani\u0107 M (2008) Recent developments on graphs of bounded clique-width. Discrete Appl Math. In press","DOI":"10.1016\/j.dam.2008.08.022"},{"key":"9260_CR24","unstructured":"Kant\u00e9 MM (2008) Graph structurings: Some algorithmic applications. PhD thesis, Universit\u00e9 Bordeaux 1, Bordeaux"},{"key":"9260_CR25","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1007\/978-3-540-79723-4_3","volume-title":"International workshop on parameterized and exact computation (IWPEC)","author":"S Kreutzer","year":"2008","unstructured":"Kreutzer S (2008) Algorithmic meta-theorems. In: Grohe M, Neidermeier R (eds) International workshop on parameterized and exact computation (IWPEC). LNCS, vol 5018. Springer, Berlin, pp 10\u201312. A\u00a0full version is available at arXiv:0902.3616v1"},{"key":"9260_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of finite model theory","author":"L Libkin","year":"2004","unstructured":"Libkin L (2004) Elements of finite model theory. Springer, Berlin"},{"key":"9260_CR27","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1007\/978-3-540-92182-0_76","volume-title":"International symposium on algorithms and computation (ISAAC)","author":"V Lozin","year":"2008","unstructured":"Lozin V (2008) From tree-width to clique-width: excluding a unit-interval graph. In: Hong S, Nagamochi H, Fukunaga T (eds) International symposium on algorithms and computation (ISAAC). LNCS, vol 5369. Springer, Berlin, pp 871\u2013882"},{"key":"9260_CR28","first-page":"391","volume-title":"38th annual ACM symposium on theory of computing (STOC)","author":"J Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il J, Ossona de Mendez P (2006) Linear time low tree-width partitions and algorithmic consequences. In: Kleinberg JM (ed) 38th annual ACM symposium on theory of computing (STOC). ACM, New York, pp 391\u2013400"},{"issue":"4","key":"9260_CR29","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum S, Seymour P (2006) Approximating clique-width and branch-width. J Comb Theory, Ser B 96(4):514\u2013528","journal-title":"J Comb Theory, Ser B"},{"issue":"6","key":"9260_CR30","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1017\/S0960129500070079","volume":"6","author":"D Seese","year":"1996","unstructured":"Seese D (1996) Linear time computable problems and first-order descriptions. Math Struct Comput Sci 6(6):505\u2013526","journal-title":"Math Struct Comput Sci"},{"issue":"14","key":"9260_CR31","doi-asserted-by":"crossref","first-page":"1885","DOI":"10.1016\/j.dam.2007.03.014","volume":"155","author":"K Suchan","year":"2007","unstructured":"Suchan K, Todinca I (2007) On powers of graphs of bounded NLC-width (Clique-Width). Discrete Appl Math 155(14):1885\u20131893","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9260-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9260-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9260-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9260-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,27]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["9260"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9260-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,27]]}}}