Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
type: Item
instance of: scholarly article
title: Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
zbMATH Open document ID: 1264.05131
author: Danny Hermelin
author: Michael R. Fellows
author: Frances Rosamond
published in: Algorithmica
publication date: 2012-11-21T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6109457
zbMATH Keywords: well quasi order
zbMATH Keywords: treewidth
zbMATH Keywords: tree decomposition
zbMATH Keywords: bounded vertex cover
zbMATH Keywords: bounded feedback vertex set
zbMATH Keywords: bounded circumference
zbMATH Keywords: parameterized complexity
zbMATH Keywords: exact algorithm
zbMATH Keywords: meta algorithm
zbMATH Keywords: intersection graph
zbMATH Keywords: string graph
Wikidata QID: Q57359664
MaRDI profile type: Publication
full work available at URL: s00453-011-9545-y
OpenAlex ID: W2148842617
cites work: Q3579375
cites work: Faster Parameterized Algorithms for Minor Containment
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Unit disk graph recognition is NP-hard
cites work: A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Induced subgraphs and well‐quasi‐ordering
cites work: Bidimensionality: new connections between FPT algorithms and PTASs
cites work: Subgraphs and well‐quasi‐ordering
cites work: Subgraph Isomorphism in Planar Graphs and Related Problems
cites work: Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
cites work: On the complexity of some colorful problems parameterized by treewidth
cites work: Nonconstructive tools for proving polynomial-time decidability
cites work: On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
cites work: Graph Layout Problems Parameterized by Vertex Cover
cites work: Bidimensionality and Geometric Graphs
cites work: Graph-modeled data clustering: Exact algorithms for clique generation
cites work: Ordering by Divisibility in Abstract Algebras
cites work: Q3113682
cites work: Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
cites work: String graphs. I: The number of critical nonstring graphs is infinite
cites work: String graphs. II: Recognizing string graphs is NP-hard
cites work: Isomorphism for Graphs of Bounded Feedback Vertex Set Number
cites work: Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
cites work: Algorithmic Meta-theorems for Restrictions of Treewidth
cites work: Q3326858
cites work: Q3821580
cites work: A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
cites work: Min Cut is NP-complete for edge weighted trees
cites work: Q5734436
cites work: Reflections on Multivariate Algorithmics and Problem Parameterization
cites work: Q5710169
cites work: Recognizing string graphs is decidable
cites work: Letter graphs and well-quasi-order by induced subgraphs
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. XX: Wagner's conjecture
cites work: Graph minors XXIII. Nash-Williams' immersion conjecture
cites work: Decidability of string graphs
cites work: Recognizing string graphs in NP
cites work: Graphs without \(K_ 4\) and well-quasi-ordering
cites work: The Complexity of the Partial Order Dimension Problem
DOI: 10.1007/S00453-011-9545-Y
description: scientific article; zbMATH DE number 6109457