K4 << The VACS Page >> AK3

Phase 1 of the program uses finite-state congruences and testsets to find obstructions sets for the various graph families that are closed under the minor order. The phase 1 program is comprised of over 80,000 lines of C++ code, and makes heavy use of C++ specific features such as templates and inheritence. Several small fixed-parameter familes have been characterized (see references below).

Phase 2 involves the generation of graph-family specific path/tree automata, parsing graphs for path/tree decompositions, and benchmarking with computed approximation algorithms. The phase 2 program will utilize the class library that has been developed for phase 1, and extend the library to handle the new data types that are required.

Kevin Cattell and Michael J. Dinneen, ``A Characterization of Graphs with Vertex Cover up to Five'' , ORDAL'94, Lecture Notes in Computer Science, volume 831, pages 86-99, July 1994

Kevin Cattell and Michael J. Dinneen and Michael R. Fellows, ``A Simple Linear-Time Algorithm for Finding Path-Decompositions of Small Width'' , IPL, volume 57, pages 197-203, 1996. (seminar slides)

Kevin Cattell and Michael J. Dinneen and Michael R. Fellows, ``Obstructions to Within a Few Vertices or Edges of Acyclic'' , accepted WADS'95, Lecture Notes in Computer Science, volume 955, pages 415-427, August 1995.

Michael J. Dinneen, Kevin Cattell and Michael R. Fellows. ``Forbidden Minors to Graphs with Small Feedback Sets'', submitted 1996. (A shorter Discrete Mathematics 2001 version is also available)
[Old paper: Kevin Cattell and Michael J. Dinneen and Michael R. Fellows, ``Finding Minor-Order Obstruction Sets: Feedback Vertex Set < = 2'', UVic 1995]

Michael J. Dinneen, Bounded Combinatorial Width and Forbidden Substructures, Ph.D. Dissertation, University of Victoria, Victoria, B.C. (1995).

Kevin Cattell, Michael J. Dinneen, Rodney G. Downey, Michael R. Fellows and Michael A. Langston. ``On Computing Graph Minor Obstruction Sets'', Theoretical Computer Science A, 233(1-2):107--127, Feb 2000.

Michael J. Dinneen. ``Too many minor order obstructions (for parameterized lower ideals)'', Journal of Universal Computer Science, 3:11 (1997), 1199-1206.

Michael J. Dinneen and Liu Xiong. ``The minor-order obstructions for the graphs of vertex cover six.'' Report CDMTCS-118, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, New Zealand. (A shorter version appears in J. of Graph Theory, 41(3):163--178, September 2002.) Fixed drawings of some of the obstructions presented in the figures of these papers are here.

Michael J. Dinneen and Rongwei Lai. ``Properties of vertex cover obstructions.'' Report CDMTCS-254, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, New Zealand. 2004 (Also appeared Discrete Mathematics 30:2484-2500, 2007.)

Michael J. Dinneen and Ralph Versteegen. ``Obstructions for the Graphs of Vertex Cover Seven.'' Report CDMTCS-430, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, New Zealand. 2012 (Electronic versions of obstructions in t-parse and matrix formats.)

Andrew Probert and Michaeli J. Dinneen. ``Branchwidth, Branch Decompositions and b-parses.'' Report CDMTCS-437, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, New Zealand. 2013 (seminar slides)