@Article{         Courcelle:1991,
  Author        = "Courcelle, Bruno",
  Abstract      = "The graph minor theorem [N. Robertson and P. Seymour, J. Comb. Theory B 35, 39-61 (1983; Zbl 0521.05062)] states that every minor- closed set of finite graphs is characterized by a finite, canonical set of forbidden configurations called its obstruction set. (This definition is relative to an ordering on graphs called minor inclusion that we shall denote by ⊴; see the appendix for a quick review of definitions). The proof of the theorem does not indicate how the obstruction set of a given minor-closed set of graphs can be computed. The obstruction sets of the set of partial k-trees are explicitely known for k at most 3 S. Arnborg, A. Proskurowski and D. G. Corneil [Discrete Math. 80(1), 1-19 (1990; Zbl 0701.05016)]. For general k, they consist of partial (k+1)-trees. The results of J. Lagergren [Algorithms and forbidden minors for tree-decomposable graphs, Ph. D., Report TRITA-NA-9104, Royal Institute of Technology, Stockholm/Sweden] provide an algorithm for obtaining them. However, this algorithm seems hard to implement. We briefly survey several equivalent ways of specifying minor-closed subclasses of partial k-trees, and we discuss some effectivity problems concerning these characterizations. We then consider these problems in the case of words (we can consider words as graphs of a special form)",
  date-added    = "2016-01-12 14:31:03 +0000",
  date-modified = "2016-01-12 14:33:30 +0000",
  Journal       = "Bulletin of EATCS",
  Title         = "On constructing obstruction sets of words",
  Year          = "1991",
  File          = "On constructing obstruction sets of words - Courcelle (0) (0) - a - a - q.pdf"
}

@Article{ Courcelle:1991, Author = "Courcelle, Bruno", Abstract = "The graph minor theorem [N. Robertson and P. Seymour, J. Comb. Theory B 35, 39-61 (1983; Zbl 0521.05062)] states that every minor- closed set of finite graphs is characterized by a finite, canonical set of forbidden configurations called its obstruction set. (This definition is relative to an ordering on graphs called minor inclusion that we shall denote by ⊴; see the appendix for a quick review of definitions). The proof of the theorem does not indicate how the obstruction set of a given minor-closed set of graphs can be computed. The obstruction sets of the set of partial k-trees are explicitely known for k at most 3 S. Arnborg, A. Proskurowski and D. G. Corneil [Discrete Math. 80(1), 1-19 (1990; Zbl 0701.05016)]. For general k, they consist of partial (k+1)-trees. The results of J. Lagergren [Algorithms and forbidden minors for tree-decomposable graphs, Ph. D., Report TRITA-NA-9104, Royal Institute of Technology, Stockholm/Sweden] provide an algorithm for obtaining them. However, this algorithm seems hard to implement. We briefly survey several equivalent ways of specifying minor-closed subclasses of partial k-trees, and we discuss some effectivity problems concerning these characterizations. We then consider these problems in the case of words (we can consider words as graphs of a special form)", date-added = "2016-01-12 14:31:03 +0000", date-modified = "2016-01-12 14:33:30 +0000", Journal = "Bulletin of EATCS", Title = "On constructing obstruction sets of words", Year = "1991", File = "On constructing obstruction sets of words - Courcelle (0) (0) - a - a - q.pdf" }