Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications (Q1759678)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
scientific article

    Statements

    Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    21 November 2012
    0 references
    Certain partial orders on graphs become well quasi orders when restricted to certain classes of graphs. Here the partial orders refine minors, defined by vertex deletion, edge deletion, edge contraction or topological contraction. Parameters such as treewidth, vertex cover number or circumference define the classes considered. Two sophisticated tools are used to show that graphs of bounded vertex cover are well quasi ordered by induced subgraphs, graphs of bounded feedback vertex set are well quasi ordered by the topological minors, and graphs of bounded circumference are well quasi ordered by the induced minors. These well quasi orderings enable fixed parameter algorithms (the bound on the graph parameter is fixed) recognizing graph families in these classes which are closed under the corresponding order. A conference version appeared in [Proceedings of IWPEC 2009, Lect.\ Notes Comput.\ 5917, 149--160 (2009; Zbl 1264.68120)].
    0 references
    well quasi order
    0 references
    treewidth
    0 references
    tree decomposition
    0 references
    bounded vertex cover
    0 references
    bounded feedback vertex set
    0 references
    bounded circumference
    0 references
    parameterized complexity
    0 references
    exact algorithm
    0 references
    meta algorithm
    0 references
    intersection graph
    0 references
    string graph
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers