Faster parameterized algorithms for minor containment
DOI10.1016/J.TCS.2011.09.015zbMATH Open1228.68035OpenAlexW1989055377WikidataQ60488564 ScholiaQ60488564MaRDI QIDQ650942FDOQ650942
Authors: Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos 
Publication date: 7 December 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.015
Recommendations
- Faster parameterized algorithms for minor containment
- Faster Parameterized Algorithms for Minimum Fill-In
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- A faster parametric minimum-cut algorithm
- Quickly deciding minor-closed parameters in general graphs
- Exponential time improvement for min-wise based algorithms
- Exponential time improvement for min-wise based algorithms
- scientific article; zbMATH DE number 7561500
- Fast algorithms for min independent dominating set
dynamic programminggraph minorsparameterized complexitygraphs on surfacesbranchwidthgraph minor containment
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph minors (05C83)
Cites Work
- Title not available (Why is that?)
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Graph minors. XX: Wagner's conjecture
- Call routing and the ratcatcher
- Graph minors. XIII: The disjoint paths problem
- Graphs on surfaces
- Nonconstructive tools for proving polynomial-time decidability
- Title not available (Why is that?)
- Quickly excluding a planar graph
- The disjoint paths problem in quadratic time
- Title not available (Why is that?)
- The graph genus problem is NP-complete
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Subexponential parameterized algorithms
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Branch decompositions and minor containment
- Title not available (Why is that?)
- Planar subgraph isomorphism revisited
- Title not available (Why is that?)
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Title not available (Why is that?)
- Dynamic programming for graphs on surfaces
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Fast minor testing in planar graphs
- Hadwiger's conjecture is decidable
Cited In (19)
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Fast minor testing in planar graphs
- Hard combinatorial problems and minor embeddings on lattice graphs
- Faster parameterized algorithms for modification problems to minor-closed classes
- Fast minor testing in planar graphs
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- A more accurate view of the flat wall theorem
- Branch decompositions and minor containment
- Graph minors from simulated annealing for annealing machines with sparse connectivity
- Adiabatic quantum programming: minor embedding with hard faults
- Differential geometric treewidth estimation in adiabatic quantum computation
- Minor embedding in broken chimera and derived graphs is NP-complete
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Faster parameterized algorithms for minor containment
- Explicit linear kernels for packing problems
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Quickly deciding minor-closed parameters in general graphs
This page was built for publication: Faster parameterized algorithms for minor containment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650942)
