The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
RAIRO-Theor. Inf. Appl., 26 3 (1992) 257-286
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
Compound Logics for Modification Problems
Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis and Dimitrios M. ThilikosACM Transactions on Computational Logic 26 (1) 1 (2025)
https://doi.org/10.1145/3696451
15536 60 (2025)
https://doi.org/10.1007/978-3-031-83438-7_6
14462 43 (2024)
https://doi.org/10.1007/978-3-031-49614-1_3
Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi and Yota OtachiAlgorithmica 86 (11) 3395 (2024)
https://doi.org/10.1007/s00453-024-01261-0
How I got to like graph polynomials
Johann A. MakowskyModel Theory 3 (2) 465 (2024)
https://doi.org/10.2140/mt.2024.3.465
Extended MSO Model Checking via Small Vertex Integrity
Tatsuya Gima and Yota OtachiAlgorithmica 86 (1) 147 (2024)
https://doi.org/10.1007/s00453-023-01161-9
Algorithms and Discrete Applied Mathematics
Sriram Bhyravarapu and I. Vinod ReddyLecture Notes in Computer Science, Algorithms and Discrete Applied Mathematics 13947 159 (2023)
https://doi.org/10.1007/978-3-031-25211-2_12
1 (2023)
https://doi.org/10.1109/LICS56636.2023.10175832
A general framework for path convexities
João Vinicius C. Thompson, Loana T. Nogueira, Fábio Protti, et al.Journal of Combinatorial Optimization 43 (5) 994 (2022)
https://doi.org/10.1007/s10878-020-00618-9
Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics
Bertrand Marchand, Yann Ponty and Laurent BulteauAlgorithms for Molecular Biology 17 (1) (2022)
https://doi.org/10.1186/s13015-022-00213-z
Exploring the gap between treedepth and vertex cover through vertex integrity
Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi and Yota OtachiTheoretical Computer Science 918 60 (2022)
https://doi.org/10.1016/j.tcs.2022.03.021
886 (2022)
https://doi.org/10.1145/3519935.3519996
Parameterized Complexity of $$(A,\ell )$$-Path Packing
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, et al.Algorithmica 84 (4) 871 (2022)
https://doi.org/10.1007/s00453-021-00875-y
A polynomial time algorithm to compute the connected treewidth of a series–parallel graph
Guillaume Mescoff, Christophe Paul and Dimitrios M. ThilikosDiscrete Applied Mathematics 312 72 (2022)
https://doi.org/10.1016/j.dam.2021.02.039
An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis and Dimitrios M. ThilikosACM Transactions on Computation Theory 14 (3-4) 1 (2022)
https://doi.org/10.1145/3571278
Vertex partitioning problems on graphs with bounded tree width
N.R. Aravind, Subrahmanyam Kalyanasundaram and Anjeneya Swami KareDiscrete Applied Mathematics 319 254 (2022)
https://doi.org/10.1016/j.dam.2021.05.016
Algorithms and Complexity
Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi and Yota OtachiLecture Notes in Computer Science, Algorithms and Complexity 12701 271 (2021)
https://doi.org/10.1007/978-3-030-75242-2_19
(2021)
https://doi.org/10.1101/2021.04.30.442158
Treewidth, Kernels, and Algorithms
Dimitrios M. ThilikosLecture Notes in Computer Science, Treewidth, Kernels, and Algorithms 12160 222 (2020)
https://doi.org/10.1007/978-3-030-42071-0_16
12126 43 (2020)
https://doi.org/10.1007/978-3-030-48966-3_4
Treewidth, Kernels, and Algorithms
Yota OtachiLecture Notes in Computer Science, Treewidth, Kernels, and Algorithms 12160 165 (2020)
https://doi.org/10.1007/978-3-030-42071-0_12
On caterpillar factors in graphs
Csilla Bujtás, Stanislav Jendroľ and Zsolt TuzaTheoretical Computer Science 846 82 (2020)
https://doi.org/10.1016/j.tcs.2020.09.022
Finding a potential community in networks
Cristina Bazgan, Thomas Pontoizeau and Zsolt TuzaTheoretical Computer Science 769 32 (2019)
https://doi.org/10.1016/j.tcs.2018.10.011
Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Paloma T. Lima and Daniël PaulusmaAlgorithmica 81 (7) 2795 (2019)
https://doi.org/10.1007/s00453-019-00555-y
Clique-width III
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav ZehaviACM Transactions on Algorithms 15 (1) 1 (2019)
https://doi.org/10.1145/3280824
11640 272 (2019)
https://doi.org/10.1007/978-3-030-27195-4_25
11394 231 (2019)
https://doi.org/10.1007/978-3-030-11509-8_19
11485 38 (2019)
https://doi.org/10.1007/978-3-030-17402-6_4
Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity
Hans L. Bodlaender, Hirotaka Ono and Yota OtachiAlgorithmica 80 (7) 2160 (2018)
https://doi.org/10.1007/s00453-017-0399-9
Computing square roots of graphs with low maximum degree
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma and Anthony StewartDiscrete Applied Mathematics 248 93 (2018)
https://doi.org/10.1016/j.dam.2017.04.041
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
Konrad K. Dabrowski, Vadim V. Lozin and Daniël PaulusmaOrder 35 (2) 253 (2018)
https://doi.org/10.1007/s11083-017-9430-7
Finding Cactus Roots in Polynomial Time
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma and Anthony StewartTheory of Computing Systems 62 (6) 1409 (2018)
https://doi.org/10.1007/s00224-017-9825-2
Safe sets in graphs: Graph classes and structural parameters
Raquel Águeda, Nathann Cohen, Shinya Fujita, et al.Journal of Combinatorial Optimization 36 (4) 1221 (2018)
https://doi.org/10.1007/s10878-017-0205-2
Linear kernels for k-tuple and liar’s domination in bounded genus graphs
Arijit Bishnu, Arijit Ghosh and Subhabrata PaulDiscrete Applied Mathematics 231 67 (2017)
https://doi.org/10.1016/j.dam.2016.06.008
MSOL restricted contractibility to planar graphs
James Abello, Pavel Klavík, Jan Kratochvíl and Tomáš VyskočilTheoretical Computer Science 676 1 (2017)
https://doi.org/10.1016/j.tcs.2017.02.030
A linear kernel for finding square roots of almost planar graphs
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma and Anthony StewartTheoretical Computer Science 689 36 (2017)
https://doi.org/10.1016/j.tcs.2017.05.008
Uniform Kernelization Complexity of Hitting Forbidden Minors
Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov and Saket SaurabhACM Transactions on Algorithms 13 (3) 1 (2017)
https://doi.org/10.1145/3029051
Combinatorial Problems on H-graphs
Steven Chaplick and Peter ZemanElectronic Notes in Discrete Mathematics 61 223 (2017)
https://doi.org/10.1016/j.endm.2017.06.042
10236 80 (2017)
https://doi.org/10.1007/978-3-319-57586-5_8
Combinatorial Optimization and Applications
Raquel Águeda, Nathann Cohen, Shinya Fujita, et al.Lecture Notes in Computer Science, Combinatorial Optimization and Applications 10043 241 (2016)
https://doi.org/10.1007/978-3-319-48749-6_18
1 (2016)
https://doi.org/10.1145/2902251.2902305
Combinatorial Algorithms
Konrad K. Dabrowski, Vadim V. Lozin and Daniël PaulusmaLecture Notes in Computer Science, Combinatorial Algorithms 9843 253 (2016)
https://doi.org/10.1007/978-3-319-44543-4_20
(Meta) Kernelization
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, et al.Journal of the ACM 63 (5) 1 (2016)
https://doi.org/10.1145/2973749
(1,j)-set problem in graphs
Arijit Bishnu, Kunal Dutta, Arijit Ghosh and Subhabrata PaulDiscrete Mathematics 339 (10) 2515 (2016)
https://doi.org/10.1016/j.disc.2016.04.008
Large Induced Subgraphs via Triangulations and CMSO
Fedor V. Fomin, Ioan Todinca and Yngve VillangerSIAM Journal on Computing 44 (1) 54 (2015)
https://doi.org/10.1137/140964801
Modifying a Graph Using Vertex Elimination
Petr A. Golovach, Pinar Heggernes, Pim van ’t Hof, et al.Algorithmica 72 (1) 99 (2015)
https://doi.org/10.1007/s00453-013-9848-2
Partitioning a graph into disjoint cliques and a triangle-free graph
Faisal N. Abu-Khzam, Carl Feghali and Haiko MüllerDiscrete Applied Mathematics 190-191 1 (2015)
https://doi.org/10.1016/j.dam.2015.03.015
Complexity and algorithms for recognizing polar and monopolar graphs
Van Bang Le and Ragnar NevriesTheoretical Computer Science 528 1 (2014)
https://doi.org/10.1016/j.tcs.2014.01.032
Algorithms for unipolar and generalized split graphs
Elaine M. Eschen and Xiaoqiang WangDiscrete Applied Mathematics 162 195 (2014)
https://doi.org/10.1016/j.dam.2013.08.011
Handbook of Graph Theory, Second Edition
Richard Borie, R Parker and Craig ToveyDiscrete Mathematics and Its Applications, Handbook of Graph Theory, Second Edition 20134658 101 (2013)
https://doi.org/10.1201/b16132-11
Polar permutation graphs are polynomial-time recognisable
Tınaz Ekim, Pinar Heggernes and Daniel MeisterEuropean Journal of Combinatorics 34 (3) 576 (2013)
https://doi.org/10.1016/j.ejc.2011.12.007
Does Treewidth Help in Modal Satisfiability?
M. PraveenACM Transactions on Computational Logic 14 (3) 1 (2013)
https://doi.org/10.1145/2499937.2499939
Fundamentals of Parameterized Complexity
Rodney G. Downey and Michael R. FellowsTexts in Computer Science, Fundamentals of Parameterized Complexity 265 (2013)
https://doi.org/10.1007/978-1-4471-5559-1_13
Graph-Theoretic Concepts in Computer Science
Haiko MüllerLecture Notes in Computer Science, Graph-Theoretic Concepts in Computer Science 7551 148 (2012)
https://doi.org/10.1007/978-3-642-34611-8_17
The complexity of two graph orientation problems
Nicole Eggemann and Steven D. NobleDiscrete Applied Mathematics 160 (4-5) 513 (2012)
https://doi.org/10.1016/j.dam.2011.10.036
Automata for the verification of monadic second-order graph properties
Bruno Courcelle and Irène DurandJournal of Applied Logic 10 (4) 368 (2012)
https://doi.org/10.1016/j.jal.2011.07.001
LATIN 2012: Theoretical Informatics
Fedor V. Fomin, Serge Gaspers, Petr Golovach, et al.Lecture Notes in Computer Science, LATIN 2012: Theoretical Informatics 7256 350 (2012)
https://doi.org/10.1007/978-3-642-29344-3_30
Parameterized Complexity of the Spanning Tree Congestion Problem
Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi and Erik Jan van LeeuwenAlgorithmica 64 (1) 85 (2012)
https://doi.org/10.1007/s00453-011-9565-7
Algorithms and Computation
Van Bang Le and Ragnar NevriesLecture Notes in Computer Science, Algorithms and Computation 7074 120 (2011)
https://doi.org/10.1007/978-3-642-25591-5_14
Confronting intractability via parameters
Rodney G. Downey and Dimitrios M. ThilikosComputer Science Review 5 (4) 279 (2011)
https://doi.org/10.1016/j.cosrev.2011.09.002
Monadic second-order model-checking on decomposable matroids
Yann StrozeckiDiscrete Applied Mathematics 159 (10) 1022 (2011)
https://doi.org/10.1016/j.dam.2011.02.005
Complexity and approximation of the Constrained Forest problem
Cristina Bazgan, Basile Couëtoux and Zsolt TuzaTheoretical Computer Science 412 (32) 4081 (2011)
https://doi.org/10.1016/j.tcs.2010.07.018
Algorithms and Computation
Cristina Bazgan, Morgan Chopin and Michael R. FellowsLecture Notes in Computer Science, Algorithms and Computation 7074 643 (2011)
https://doi.org/10.1007/978-3-642-25591-5_66
Designing Low-Congestion Networks with Structural Graph Theory
Yota OTACHIInterdisciplinary Information Sciences 17 (3) 197 (2011)
https://doi.org/10.4036/iis.2011.197
Satisfactory graph partition, variants, and generalizations
Cristina Bazgan, Zsolt Tuza and Daniel VanderpootenEuropean Journal of Operational Research 206 (2) 271 (2010)
https://doi.org/10.1016/j.ejor.2009.10.019
Graph Theoretic Concepts in Computer Science
Yota Otachi, Hans L. Bodlaender and Erik Jan van LeeuwenLecture Notes in Computer Science, Graph Theoretic Concepts in Computer Science 6410 3 (2010)
https://doi.org/10.1007/978-3-642-16926-7_3
Intractability of Clique-Width Parameterizations
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov and Saket SaurabhSIAM Journal on Computing 39 (5) 1941 (2010)
https://doi.org/10.1137/080742270
Exakte Algorithmen für schwere Graphenprobleme
Frank Gurski, Irene Rothe, Jörg Rothe and Egon WankeeXamen.press, Exakte Algorithmen für schwere Graphenprobleme 259 (2010)
https://doi.org/10.1007/978-3-642-04500-4_10
Treewidth and logical definability of graph products
Selma DjelloulTheoretical Computer Science 410 (8-10) 696 (2009)
https://doi.org/10.1016/j.tcs.2008.10.019
Tree-width of graphs without a 3×3 grid minor
E. Birmelé, J.A. Bondy and B.A. ReedDiscrete Applied Mathematics 157 (12) 2577 (2009)
https://doi.org/10.1016/j.dam.2008.08.003
Combinatorial Algorithms
Tınaz Ekim, Pinar Heggernes and Daniel MeisterLecture Notes in Computer Science, Combinatorial Algorithms 5874 218 (2009)
https://doi.org/10.1007/978-3-642-10217-2_23
Algorithms and Computation
Cristina Bazgan, Basile Couëtoux and Zsolt TuzaLecture Notes in Computer Science, Algorithms and Computation 5878 892 (2009)
https://doi.org/10.1007/978-3-642-10631-6_90
Solving problems on recursively constructed graphs
Richard B. Borie, R. Gary Parker and Craig A. ToveyACM Computing Surveys 41 (1) 1 (2009)
https://doi.org/10.1145/1456650.1456654
Argumentation in Artificial Intelligence
Paul E. Dunne and Michael WooldridgeArgumentation in Artificial Intelligence 85 (2009)
https://doi.org/10.1007/978-0-387-98197-0_5
Graph-Theoretic Concepts in Computer Science
Jiří Fiala and Petr A. GolovachLecture Notes in Computer Science, Graph-Theoretic Concepts in Computer Science 5344 134 (2008)
https://doi.org/10.1007/978-3-540-92248-3_13
From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials
J. A. MakowskyTheory of Computing Systems 43 (3-4) 542 (2008)
https://doi.org/10.1007/s00224-007-9022-9
MSOL partitioning problems on graphs of bounded treewidth and clique-width
Michaël RaoTheoretical Computer Science 377 (1-3) 260 (2007)
https://doi.org/10.1016/j.tcs.2007.03.043
Combinatorial and computational aspects of graph packing and graph decomposition
Raphael YusterComputer Science Review 1 (1) 12 (2007)
https://doi.org/10.1016/j.cosrev.2007.07.002
Frontiers in Algorithmics
Detlef SeeseLecture Notes in Computer Science, Frontiers in Algorithmics 4613 293 (2007)
https://doi.org/10.1007/978-3-540-73814-5_28
Computational properties of argument systems satisfying graph-theoretic constraints
Paul E. DunneArtificial Intelligence 171 (10-15) 701 (2007)
https://doi.org/10.1016/j.artint.2007.03.006
The relative clique-width of a graph
Vadim Lozin and Dieter RautenbachJournal of Combinatorial Theory, Series B 97 (5) 846 (2007)
https://doi.org/10.1016/j.jctb.2007.04.001
Degree-constrained decompositions of graphs: Bounded treewidth and planarity
Cristina Bazgan, Zsolt Tuza and Daniel VanderpootenTheoretical Computer Science 355 (3) 389 (2006)
https://doi.org/10.1016/j.tcs.2006.01.024
Trees, grids, and MSO decidability: From graphs to matroids
Petr Hliněný and Detlef SeeseTheoretical Computer Science 351 (3) 372 (2006)
https://doi.org/10.1016/j.tcs.2005.10.006
Graph decompositions for cartesian products
Selma DjelloulElectronic Notes in Discrete Mathematics 22 375 (2005)
https://doi.org/10.1016/j.endm.2005.06.073
Chordal bipartite graphs of bounded tree- and clique-width
V. Lozin and D. RautenbachDiscrete Mathematics 283 (1-3) 151 (2004)
https://doi.org/10.1016/j.disc.2004.02.008
On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
V. Lozin and D. RautenbachSIAM Journal on Discrete Mathematics 18 (1) 195 (2004)
https://doi.org/10.1137/S0895480102419755
Querying Linguistic Treebanks with Monadic Second-Order Logic in Linear Time
Stephan KepserJournal of Logic, Language and Information 13 (4) 457 (2004)
https://doi.org/10.1007/s10849-004-2116-8
Exploiting structure in quantified formulas
Richard E. Stearns and Harry B. HuntJournal of Algorithms 43 (2) 220 (2002)
https://doi.org/10.1016/S0196-6774(02)00002-0
Counting H-colorings of partial k-trees
Josep Díaz, Maria Serna and Dimitrios M. ThilikosTheoretical Computer Science 281 (1-2) 291 (2002)
https://doi.org/10.1016/S0304-3975(02)00017-8
Automata-based Representations for Infinite Graphs
Salvatore La Torre and Margherita NapoliRAIRO - Theoretical Informatics and Applications 35 (4) 311 (2001)
https://doi.org/10.1051/ita:2001122
Upper bounds to the clique width of graphs
Bruno Courcelle and Stephan OlariuDiscrete Applied Mathematics 101 (1-3) 77 (2000)
https://doi.org/10.1016/S0166-218X(99)00184-5
The obstructions of a minor-closed set of graphs defined by a context-free grammar
B Courcelle and G SénizerguesDiscrete Mathematics 182 (1-3) 29 (1998)
https://doi.org/10.1016/S0012-365X(97)83079-8
Mathematical Foundations of Computer Science 1998
Klaus BarthelmannLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1998 1450 543 (1998)
https://doi.org/10.1007/BFb0055804
Mathematical Foundations of Computer Science 1998
Salvatore La Torre and Margherita NapoliLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1998 1450 571 (1998)
https://doi.org/10.1007/BFb0055807
Handbook of Formal Languages
Joost EngelfrietHandbook of Formal Languages 125 (1997)
https://doi.org/10.1007/978-3-642-59126-6_3
Graph Grammars and Their Application to Computer Science
B. Courcelle and G. SénizerguesLecture Notes in Computer Science, Graph Grammars and Their Application to Computer Science 1073 351 (1996)
https://doi.org/10.1007/3-540-61228-9_98
On Linear Recognition of Tree-Width at Most Four
Daniel P. SandersSIAM Journal on Discrete Mathematics 9 (1) 101 (1996)
https://doi.org/10.1137/S0895480193243043
Characterization and complexity of uniformly nonprimitive labeled 2-structures
J. Engelfriet, T. Harju, A. Proskurowski and G. RozenbergTheoretical Computer Science 154 (2) 247 (1996)
https://doi.org/10.1016/0304-3975(94)00272-X
Equivalent definitions of recognizability for sets of graphs of bounded tree-width
Bruno Courcelle and Jens LagergrenMathematical Structures in Computer Science 6 (2) 141 (1996)
https://doi.org/10.1017/S096012950000092X
Graph Grammars and Their Application to Computer Science
Stefan Arnborg and Andrzej ProskurowskiLecture Notes in Computer Science, Graph Grammars and Their Application to Computer Science 1073 469 (1996)
https://doi.org/10.1007/3-540-61228-9_106