Faster parameterized algorithms for minor containment
type: Item
instance of: scholarly article
title: Faster parameterized algorithms for minor containment
zbMATH Open document ID: 1228.68035
author: Isolde Adler
author: Frederic Dorn
author: Fedor V. Fomin
author: Ignasi Sau
author: Dimitrios M. Thilikos
published in: Theoretical Computer Science
publication date: 2011-12-07T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 5987019
zbMATH Keywords: graph minors
zbMATH Keywords: branchwidth
zbMATH Keywords: graph minor containment
zbMATH Keywords: parameterized complexity
zbMATH Keywords: dynamic programming
zbMATH Keywords: graphs on surfaces
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.09.015
OpenAlex ID: W1989055377
Wikidata QID: Q60488564
cites work: Fast Minor Testing in Planar Graphs
cites work: Q3579375
cites work: Q4385531
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
cites work: Q5315023
cites work: Planar Subgraph Isomorphism Revisited
cites work: Q3113754
cites work: Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
cites work: Q3579494
cites work: Subexponential parameterized algorithms
cites work: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
cites work: Subgraph Isomorphism in Planar Graphs and Related Problems
cites work: Nonconstructive tools for proving polynomial-time decidability
cites work: Q4198056
cites work: Improved bounds on the planar branchwidth with respect to the largest grid minor size
cites work: Branch decompositions and minor containment
cites work: The disjoint paths problem in quadratic time
cites work: Hadwiger's conjecture is decidable
cites work: Q5365079
cites work: On the complexity of finding iso- and other morphisms for partial \(k\)- trees
cites work: Graphs on surfaces
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Quickly excluding a planar graph
cites work: Graph minors. XX: Wagner's conjecture
cites work: Dynamic Programming for Graphs on Surfaces
cites work: Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
cites work: Call routing and the ratcatcher
cites work: The graph genus problem is NP-complete
DOI: 10.1016/J.TCS.2011.09.015
Recommended article: Faster Parameterized Algorithms for Minor Containment
Recommended article: Faster Parameterized Algorithms for Minimum Fill-In
Recommended article: Faster parameterized algorithms for \textsc{Minimum Fill-in}
Recommended article: A faster parametric minimum-cut algorithm
Recommended article: Quickly deciding minor-closed parameters in general graphs
Recommended article: Exponential time improvement for min-wise based algorithms
Recommended article: Q5365021
Recommended article: Q5091155
Recommended article: Fast algorithms for min independent dominating set
description: scientific article; zbMATH DE number 5987019