EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues RAIRO-Theor. Inf. Appl., 26 3 (1992) 257-286 Article references

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):

Automata for the verification of monadic second-order graph properties

Bruno Courcelle and Irène Durand
Journal of Applied Logic 10 (4) 368 (2012)
DOI: 10.1016/j.jal.2011.07.001
See this article

Partitioning a graph into disjoint cliques and a triangle-free graph

Faisal N. Abu-Khzam, Carl Feghali and Haiko Müller
Discrete Applied Mathematics 190-191 1 (2015)
DOI: 10.1016/j.dam.2015.03.015
See this article

A linear kernel for finding square roots of almost planar graphs

Petr A. Golovach, Dieter Kratsch, Daniël Paulusma and Anthony Stewart
Theoretical Computer Science 689 36 (2017)
DOI: 10.1016/j.tcs.2017.05.008
See this article

Monadic second-order model-checking on decomposable matroids

Yann Strozecki
Discrete Applied Mathematics 159 (10) 1022 (2011)
DOI: 10.1016/j.dam.2011.02.005
See this article

Tree-width of graphs without a 3×3 grid minor

E. Birmelé, J.A. Bondy and B.A. Reed
Discrete Applied Mathematics 157 (12) 2577 (2009)
DOI: 10.1016/j.dam.2008.08.003
See this article

Graph Theoretic Concepts in Computer Science

Yota Otachi, Hans L. Bodlaender and Erik Jan van Leeuwen
Lecture Notes in Computer Science, Graph Theoretic Concepts in Computer Science 6410 3 (2010)
DOI: 10.1007/978-3-642-16926-7_3
See this article

Fedor V. Fomin and Tuukka Korhonen
886 (2022)
DOI: 10.1145/3519935.3519996
See this article

Parameterized Complexity of $$(A,\ell )$$-Path Packing

Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, et al.
Algorithmica 84 (4) 871 (2022)
DOI: 10.1007/s00453-021-00875-y
See this article

The monadic second order logic of graphs VI: on several representations of graphs by relational structures

Bruno Courcelle
Discrete Applied Mathematics 54 (2-3) 117 (1994)
DOI: 10.1016/0166-218X(94)90019-1
See this article

Combinatorial and computational aspects of graph packing and graph decomposition

Raphael Yuster
Computer Science Review 1 (1) 12 (2007)
DOI: 10.1016/j.cosrev.2007.07.002
See this article

Frontiers in Algorithmics

Detlef Seese
Lecture Notes in Computer Science, Frontiers in Algorithmics 4613 293 (2007)
DOI: 10.1007/978-3-540-73814-5_28
See this article

Handbook of Formal Languages

Joost Engelfriet
Handbook of Formal Languages 125 (1997)
DOI: 10.1007/978-3-642-59126-6_3
See this article

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity

Hans L. Bodlaender, Hirotaka Ono and Yota Otachi
Algorithmica 80 (7) 2160 (2018)
DOI: 10.1007/s00453-017-0399-9
See this article

Handbook of Graph Theory, Second Edition

Richard Borie, R Parker and Craig Tovey
Discrete Mathematics and Its Applications, Handbook of Graph Theory, Second Edition 20134658 101 (2013)
DOI: 10.1201/b16132-11
See this article

Solving problems on recursively constructed graphs

Richard B. Borie, R. Gary Parker and Craig A. Tovey
ACM Computing Surveys 41 (1) 1 (2009)
DOI: 10.1145/1456650.1456654
See this article

Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics

Bertrand Marchand, Yann Ponty and Laurent Bulteau
Algorithms for Molecular Biology 17 (1) (2022)
DOI: 10.1186/s13015-022-00213-z
See this article

Polar permutation graphs are polynomial-time recognisable

Tınaz Ekim, Pinar Heggernes and Daniel Meister
European Journal of Combinatorics 34 (3) 576 (2013)
DOI: 10.1016/j.ejc.2011.12.007
See this article

Handle-rewriting hypergraph grammars

Bruno Courcelle, Joost Engelfriet and Grzegorz Rozenberg
Journal of Computer and System Sciences 46 (2) 218 (1993)
DOI: 10.1016/0022-0000(93)90004-G
See this article

Graph-Theoretic Concepts in Computer Science

Jiří Fiala and Petr A. Golovach
Lecture Notes in Computer Science, Graph-Theoretic Concepts in Computer Science 5344 134 (2008)
DOI: 10.1007/978-3-540-92248-3_13
See this article

References

Discrete Applied Mathematics 54 (2-3) 281 (1994)
DOI: 10.1016/0166-218X(94)90028-0
See this article

Mathematical Foundations of Computer Science 1998

Salvatore La Torre and Margherita Napoli
Lecture Notes in Computer Science, Mathematical Foundations of Computer Science 1998 1450 571 (1998)
DOI: 10.1007/BFb0055807
See this article

Combinatorial Optimization and Applications

Raquel Águeda, Nathann Cohen, Shinya Fujita, et al.
Lecture Notes in Computer Science, Combinatorial Optimization and Applications 10043 241 (2016)
DOI: 10.1007/978-3-319-48749-6_18
See this article

Algorithms and Complexity

Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi and Yota Otachi
Lecture Notes in Computer Science, Algorithms and Complexity 12701 271 (2021)
DOI: 10.1007/978-3-030-75242-2_19
See this article

Upper bounds to the clique width of graphs

Bruno Courcelle and Stephan Olariu
Discrete Applied Mathematics 101 (1-3) 77 (2000)
DOI: 10.1016/S0166-218X(99)00184-5
See this article

Combinatorial Algorithms

Konrad K. Dabrowski, Vadim V. Lozin and Daniël Paulusma
Lecture Notes in Computer Science, Combinatorial Algorithms 9843 253 (2016)
DOI: 10.1007/978-3-319-44543-4_20
See this article

Vertex partitioning problems on graphs with bounded tree width

N.R. Aravind, Subrahmanyam Kalyanasundaram and Anjeneya Swami Kare
Discrete Applied Mathematics 319 254 (2022)
DOI: 10.1016/j.dam.2021.05.016
See this article

MSOL restricted contractibility to planar graphs

James Abello, Pavel Klavík, Jan Kratochvíl and Tomáš Vyskočil
Theoretical Computer Science 676 1 (2017)
DOI: 10.1016/j.tcs.2017.02.030
See this article

An algebraic theory of graph reduction

Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski and Detlef Seese
Journal of the ACM 40 (5) 1134 (1993)
DOI: 10.1145/174147.169807
See this article

Large Induced Subgraphs via Triangulations and CMSO

Fedor V. Fomin, Ioan Todinca and Yngve Villanger
SIAM Journal on Computing 44 (1) 54 (2015)
DOI: 10.1137/140964801
See this article

Satisfactory graph partition, variants, and generalizations

Cristina Bazgan, Zsolt Tuza and Daniel Vanderpooten
European Journal of Operational Research 206 (2) 271 (2010)
DOI: 10.1016/j.ejor.2009.10.019
See this article

Equivalent definitions of recognizability for sets of graphs of bounded tree-width

Bruno Courcelle and Jens Lagergren
Mathematical Structures in Computer Science 6 (2) 141 (1996)
DOI: 10.1017/S096012950000092X
See this article

Fundamentals of Parameterized Complexity

Rodney G. Downey and Michael R. Fellows
Texts in Computer Science, Fundamentals of Parameterized Complexity 265 (2013)
DOI: 10.1007/978-1-4471-5559-1_13
See this article

Argumentation in Artificial Intelligence

Paul E. Dunne and Michael Wooldridge
Argumentation in Artificial Intelligence 85 (2009)
DOI: 10.1007/978-0-387-98197-0_5
See this article

Treewidth and logical definability of graph products

Selma Djelloul
Theoretical Computer Science 410 (8-10) 696 (2009)
DOI: 10.1016/j.tcs.2008.10.019
See this article

Graph Grammars and Their Application to Computer Science

B. Courcelle and G. Sénizergues
Lecture Notes in Computer Science, Graph Grammars and Their Application to Computer Science 1073 351 (1996)
DOI: 10.1007/3-540-61228-9_98
See this article

Treewidth, Kernels, and Algorithms

Dimitrios M. Thilikos
Lecture Notes in Computer Science, Treewidth, Kernels, and Algorithms 12160 222 (2020)
DOI: 10.1007/978-3-030-42071-0_16
See this article

Uniform Kernelization Complexity of Hitting Forbidden Minors

Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov and Saket Saurabh
ACM Transactions on Algorithms 13 (3) 1 (2017)
DOI: 10.1145/3029051
See this article

Degree-constrained decompositions of graphs: Bounded treewidth and planarity

Cristina Bazgan, Zsolt Tuza and Daniel Vanderpooten
Theoretical Computer Science 355 (3) 389 (2006)
DOI: 10.1016/j.tcs.2006.01.024
See this article

On Linear Recognition of Tree-Width at Most Four

Daniel P. Sanders
SIAM Journal on Discrete Mathematics 9 (1) 101 (1996)
DOI: 10.1137/S0895480193243043
See this article

Confronting intractability via parameters

Rodney G. Downey and Dimitrios M. Thilikos
Computer Science Review 5 (4) 279 (2011)
DOI: 10.1016/j.cosrev.2011.09.002
See this article

Algorithms and Discrete Applied Mathematics

N. R. Aravind, Subrahmanyam Kalyanasundaram and Anjeneya Swami Kare
Lecture Notes in Computer Science, Algorithms and Discrete Applied Mathematics 11394 231 (2019)
DOI: 10.1007/978-3-030-11509-8_19
See this article

Algorithms and Computation

Cristina Bazgan, Morgan Chopin and Michael R. Fellows
Lecture Notes in Computer Science, Algorithms and Computation 7074 643 (2011)
DOI: 10.1007/978-3-642-25591-5_66
See this article

CAAP '92

Bruno Courcelle
Lecture Notes in Computer Science, CAAP '92 581 124 (1992)
DOI: 10.1007/3-540-55251-0_7
See this article

Querying Linguistic Treebanks with Monadic Second-Order Logic in Linear Time

Stephan Kepser
Journal of Logic, Language and Information 13 (4) 457 (2004)
DOI: 10.1007/s10849-004-2116-8
See this article

The complexity of two graph orientation problems

Nicole Eggemann and Steven D. Noble
Discrete Applied Mathematics 160 (4-5) 513 (2012)
DOI: 10.1016/j.dam.2011.10.036
See this article

Intractability of Clique-Width Parameterizations

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov and Saket Saurabh
SIAM Journal on Computing 39 (5) 1941 (2010)
DOI: 10.1137/080742270
See this article

A polynomial time algorithm to compute the connected treewidth of a series–parallel graph

Guillaume Mescoff, Christophe Paul and Dimitrios M. Thilikos
Discrete Applied Mathematics 312 72 (2022)
DOI: 10.1016/j.dam.2021.02.039
See this article

Trees, grids, and MSO decidability: From graphs to matroids

Petr Hliněný and Detlef Seese
Theoretical Computer Science 351 (3) 372 (2006)
DOI: 10.1016/j.tcs.2005.10.006
See this article

Complexity and approximation of the Constrained Forest problem

Cristina Bazgan, Basile Couëtoux and Zsolt Tuza
Theoretical Computer Science 412 (32) 4081 (2011)
DOI: 10.1016/j.tcs.2010.07.018
See this article

Exploring the gap between treedepth and vertex cover through vertex integrity

Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi and Yota Otachi
Theoretical Computer Science 918 60 (2022)
DOI: 10.1016/j.tcs.2022.03.021
See this article

Linear kernels for k-tuple and liar’s domination in bounded genus graphs

Arijit Bishnu, Arijit Ghosh and Subhabrata Paul
Discrete Applied Mathematics 231 67 (2017)
DOI: 10.1016/j.dam.2016.06.008
See this article

Modifying a Graph Using Vertex Elimination

Petr A. Golovach, Pinar Heggernes, Pim van ’t Hof, et al.
Algorithmica 72 (1) 99 (2015)
DOI: 10.1007/s00453-013-9848-2
See this article

Algorithms and Computation

Van Bang Le and Ragnar Nevries
Lecture Notes in Computer Science, Algorithms and Computation 7074 120 (2011)
DOI: 10.1007/978-3-642-25591-5_14
See this article

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)
DOI: 10.1007/s10878-020-00618-9
See this article

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Konrad K. Dabrowski, Vadim V. Lozin and Daniël Paulusma
Order 35 (2) 253 (2018)
DOI: 10.1007/s11083-017-9430-7
See this article

The monadic second-order logic of graphs VIII: Orientations

Bruno Courcelle
Annals of Pure and Applied Logic 72 (2) 103 (1995)
DOI: 10.1016/0168-0072(95)94698-V
See this article

Chordal bipartite graphs of bounded tree- and clique-width

V. Lozin and D. Rautenbach
Discrete Mathematics 283 (1-3) 151 (2004)
DOI: 10.1016/j.disc.2004.02.008
See this article

Graph Transformations in Computer Science

Bruno Courcelle and Jens Lagergren
Lecture Notes in Computer Science, Graph Transformations in Computer Science 776 138 (1994)
DOI: 10.1007/3-540-57787-4_9
See this article

Algorithms and Discrete Applied Mathematics

Sriram Bhyravarapu and I. Vinod Reddy
Lecture Notes in Computer Science, Algorithms and Discrete Applied Mathematics 13947 159 (2023)
DOI: 10.1007/978-3-031-25211-2_12
See this article

The obstructions of a minor-closed set of graphs defined by a context-free grammar

B Courcelle and G Sénizergues
Discrete Mathematics 182 (1-3) 29 (1998)
DOI: 10.1016/S0012-365X(97)83079-8
See this article

Complexity and algorithms for recognizing polar and monopolar graphs

Van Bang Le and Ragnar Nevries
Theoretical Computer Science 528 1 (2014)
DOI: 10.1016/j.tcs.2014.01.032
See this article

An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL

Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis and Dimitrios M. Thilikos
ACM Transactions on Computation Theory 14 (3-4) 1 (2022)
DOI: 10.1145/3571278
See this article

On caterpillar factors in graphs

Csilla Bujtás, Stanislav Jendroľ and Zsolt Tuza
Theoretical Computer Science 846 82 (2020)
DOI: 10.1016/j.tcs.2020.09.022
See this article

Characterization and complexity of uniformly nonprimitive labeled 2-structures

J. Engelfriet, T. Harju, A. Proskurowski and G. Rozenberg
Theoretical Computer Science 154 (2) 247 (1996)
DOI: 10.1016/0304-3975(94)00272-X
See this article

Exakte Algorithmen für schwere Graphenprobleme

Frank Gurski, Irene Rothe, Jörg Rothe and Egon Wanke
eXamen.press, Exakte Algorithmen für schwere Graphenprobleme 259 (2010)
DOI: 10.1007/978-3-642-04500-4_10
See this article

Clique-width III

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi
ACM Transactions on Algorithms 15 (1) 1 (2019)
DOI: 10.1145/3280824
See this article

Counting H-colorings of partial k-trees

Josep Díaz, Maria Serna and Dimitrios M. Thilikos
Theoretical Computer Science 281 (1-2) 291 (2002)
DOI: 10.1016/S0304-3975(02)00017-8
See this article

Finding Cactus Roots in Polynomial Time

Petr A. Golovach, Dieter Kratsch, Daniël Paulusma and Anthony Stewart
Theory of Computing Systems 62 (6) 1409 (2018)
DOI: 10.1007/s00224-017-9825-2
See this article

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 Paulusma
Algorithmica 81 (7) 2795 (2019)
DOI: 10.1007/s00453-019-00555-y
See this article

Does Treewidth Help in Modal Satisfiability?

M. Praveen
ACM Transactions on Computational Logic 14 (3) 1 (2013)
DOI: 10.1145/2499937.2499939
See this article

Parameterized Complexity of the Spanning Tree Congestion Problem

Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi and Erik Jan van Leeuwen
Algorithmica 64 (1) 85 (2012)
DOI: 10.1007/s00453-011-9565-7
See this article

Combinatorial Algorithms

Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, et al.
Lecture Notes in Computer Science, Combinatorial Algorithms 12126 43 (2020)
DOI: 10.1007/978-3-030-48966-3_4
See this article

Exploiting structure in quantified formulas

Richard E. Stearns and Harry B. Hunt
Journal of Algorithms 43 (2) 220 (2002)
DOI: 10.1016/S0196-6774(02)00002-0
See this article

Graph-Theoretic Concepts in Computer Science

Haiko Müller
Lecture Notes in Computer Science, Graph-Theoretic Concepts in Computer Science 7551 148 (2012)
DOI: 10.1007/978-3-642-34611-8_17
See this article

Finding a potential community in networks

Cristina Bazgan, Thomas Pontoizeau and Zsolt Tuza
Theoretical Computer Science 769 32 (2019)
DOI: 10.1016/j.tcs.2018.10.011
See this article

Mathematical Foundations of Computer Science 1998

Klaus Barthelmann
Lecture Notes in Computer Science, Mathematical Foundations of Computer Science 1998 1450 543 (1998)
DOI: 10.1007/BFb0055804
See this article

Algorithms and Computation

Cristina Bazgan, Basile Couëtoux and Zsolt Tuza
Lecture Notes in Computer Science, Algorithms and Computation 5878 892 (2009)
DOI: 10.1007/978-3-642-10631-6_90
See this article

Algorithms and Complexity

Cristina Bazgan, Thomas Pontoizeau and Zsolt Tuza
Lecture Notes in Computer Science, Algorithms and Complexity 10236 80 (2017)
DOI: 10.1007/978-3-319-57586-5_8
See this article

Graph decompositions for cartesian products

Selma Djelloul
Electronic Notes in Discrete Mathematics 22 375 (2005)
DOI: 10.1016/j.endm.2005.06.073
See this article

Algorithms and Complexity

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, et al.
Lecture Notes in Computer Science, Algorithms and Complexity 11485 38 (2019)
DOI: 10.1007/978-3-030-17402-6_4
See this article

On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree

V. Lozin and D. Rautenbach
SIAM Journal on Discrete Mathematics 18 (1) 195 (2004)
DOI: 10.1137/S0895480102419755
See this article

Treewidth, Kernels, and Algorithms

Yota Otachi
Lecture Notes in Computer Science, Treewidth, Kernels, and Algorithms 12160 165 (2020)
DOI: 10.1007/978-3-030-42071-0_12
See this article

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)
DOI: 10.1007/s10878-017-0205-2
See this article

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)
DOI: 10.1007/978-3-642-29344-3_30
See this article

Combinatorial Problems on H-graphs

Steven Chaplick and Peter Zeman
Electronic Notes in Discrete Mathematics 61 223 (2017)
DOI: 10.1016/j.endm.2017.06.042
See this article

Algorithmic Aspects in Information and Management

João Vinicius C. Thompson, Loana T. Nogueira, Fábio Protti, et al.
Lecture Notes in Computer Science, Algorithmic Aspects in Information and Management 11640 272 (2019)
DOI: 10.1007/978-3-030-27195-4_25
See this article

(Meta) Kernelization

Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, et al.
Journal of the ACM 63 (5) 1 (2016)
DOI: 10.1145/2973749
See this article

A logical characterization of the sets of hypergraphs defined by Hyperedge Replacement grammars

B. Courcelle and J. Engelfriet
Mathematical Systems Theory 28 (6) 515 (1995)
DOI: 10.1007/BF01204169
See this article

Automata-based Representations for Infinite Graphs

Salvatore La Torre and Margherita Napoli
RAIRO - Theoretical Informatics and Applications 35 (4) 311 (2001)
DOI: 10.1051/ita:2001122
See this article

Computing square roots of graphs with low maximum degree

Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, et al.
Discrete Applied Mathematics 248 93 (2018)
DOI: 10.1016/j.dam.2017.04.041
See this article

Monadic second-order definable graph transductions: a survey

Bruno Courcelle
Theoretical Computer Science 126 (1) 53 (1994)
DOI: 10.1016/0304-3975(94)90268-2
See this article

Designing Low-Congestion Networks with Structural Graph Theory

Yota OTACHI
Interdisciplinary Information Sciences 17 (3) 197 (2011)
DOI: 10.4036/iis.2011.197
See this article

Computational properties of argument systems satisfying graph-theoretic constraints

Paul E. Dunne
Artificial Intelligence 171 (10-15) 701 (2007)
DOI: 10.1016/j.artint.2007.03.006
See this article

MSOL partitioning problems on graphs of bounded treewidth and clique-width

Michaël Rao
Theoretical Computer Science 377 (1-3) 260 (2007)
DOI: 10.1016/j.tcs.2007.03.043
See this article

Combinatorial Algorithms

Tınaz Ekim, Pinar Heggernes and Daniel Meister
Lecture Notes in Computer Science, Combinatorial Algorithms 5874 218 (2009)
DOI: 10.1007/978-3-642-10217-2_23
See this article

From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials

J. A. Makowsky
Theory of Computing Systems 43 (3-4) 542 (2008)
DOI: 10.1007/s00224-007-9022-9
See this article

The relative clique-width of a graph

Vadim Lozin and Dieter Rautenbach
Journal of Combinatorial Theory, Series B 97 (5) 846 (2007)
DOI: 10.1016/j.jctb.2007.04.001
See this article

Algorithms for unipolar and generalized split graphs

Elaine M. Eschen and Xiaoqiang Wang
Discrete Applied Mathematics 162 195 (2014)
DOI: 10.1016/j.dam.2013.08.011
See this article

Graph Grammars and Their Application to Computer Science

Stefan Arnborg and Andrzej Proskurowski
Lecture Notes in Computer Science, Graph Grammars and Their Application to Computer Science 1073 469 (1996)
DOI: 10.1007/3-540-61228-9_106
See this article

(1,j)-set problem in graphs

Arijit Bishnu, Kunal Dutta, Arijit Ghosh and Subhabrata Paul
Discrete Mathematics 339 (10) 2515 (2016)
DOI: 10.1016/j.disc.2016.04.008
See this article