grant@garfield.cs.mun.ca (Grant Burton) (03/14/91)
I posted an article a few days ago that wondered if the following problem was open: Let k be a fixed number, and let Pk denote the class of all graphs with treewidth bounded by k (partial k-trees). Does there exist an algorithm that, for each k, generate the obstruction set for Pk. nb. It is known that Pk is closed under minor ordering, and that the obstruction sets are different for different values of k. THIS PROBLEM IS NOT OPEN. See Jens Lagergren, "Algorithms and minimal forbidden minors for tree-decomposable graphs", University of Stockholm, Doctoral Dissertation TRITA-NA-9104, 1991. Lagergren claims to demonstrate an algorithm that generates, for each k, the obstruction set for Pk. I have not yet figured out what is going on in this paper, it is very complicated. Any algorithm, idea, response, suggestion, comment, or critique should be e-mailed to me. grant@garfield.cs.mun.ca Grant Burton Department of Computer Science Memorial University of Newfoundland St. John's, Newfoundland, Canada -- | grant@garfield.cs.mun.ca | Man said "let there be light", and there was fire. Man being lonely created | machine in the image of himself, and chaos was discovered.
grant@GARFIELD.CS.MUN.CA (Grant Burton) (03/15/91)
I posted an article a few days ago that wondered if the following problem was open: Let k be a fixed number, and let Pk denote the class of all graphs with treewidth bounded by k (partial k-trees). Does there exist an algorithm that, for each k, generate the obstruction set for Pk. nb. It is known that Pk is closed under minor ordering, and that the obstruction sets are different for different values of k. THIS PROBLEM IS NOT OPEN. See Jens Lagergren, "Algorithms and minimal forbidden minors for tree-decomposable graphs", University of Stockholm, Doctoral Dissertation TRITA-NA-9104, 1991. Lagergren claims to demonstrate an algorithm that generates, for each k, the obstruction set for Pk. I have not yet figured out what is going on in this paper, it is very complicated. Any algorithm, idea, response, suggestion, comment, or critique should be e-mailed to me. grant@garfield.cs.mun.ca Grant Burton Department of Computer Science Memorial University of Newfoundland St. John's, Newfoundland, Canada -- | grant@garfield.cs.mun.ca | Man said "let there be light", and there was fire. Man being lonely created | machine in the image of himself, and chaos was discovered.