Faster parameterized algorithms for modification problems to minor-closed classes
From MaRDI portal
Publication:6601299
DOI10.46298/theoretics.24.19zbMATH Open1547.05284MaRDI QIDQ6601299
Giannos Stamoulis, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos
Publication date: 10 September 2024
Published in: TheoretiCS (Search for Journal in Brave)
parameterized algorithmsgraph minorsobstruction setgraph modification problemsvertex deletionirrelevant vertex techniqueelimination distanceflat Wall theorem
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph isomorphism parameterized by elimination distance to bounded degree
- Irrelevant vertices for the planar disjoint paths problem
- Fundamentals of parameterized complexity
- The disjoint paths problem in quadratic time
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Forbidden graphs for tree-depth
- Sparsity. Graphs, structures, and algorithms
- Faster parameterized algorithms for minor containment
- A new proof of the flat wall theorem
- Graph minors. XX: Wagner's conjecture
- Graph minors. XXI. graphs with unique linkages
- Graph minors. V. Excluding a planar graph
- A Menger-like property of tree-width: The finite case
- The node-deletion problem for hereditary properties is NP-complete
- Upper bounds on the size of obstructions and intertwines
- Treewidth. Computations and approximations
- Graph minors. XVI: Excluding a non-planar graph
- Which problems have strongly exponential complexity?
- Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
- Cutwidth: obstructions and algorithmic aspects
- A unified treatment of linked and lean tree-decompositions
- The extremal function for complete minors
- Graph minors. XIII: The disjoint paths problem
- A Menger-like property of tree-cut width
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- Sparse obstructions for minor-covering parameters
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- Deleting vertices to graphs of bounded genus
- Fixed-parameter tractable distances to sparse graph classes
- Obtaining a planar graph by vertex deletion
- Parametrized complexity theory.
- Graph Theory
- A shorter proof of the graph minor algorithm
- Linear Rank-Width of Distance-Hereditary Graphs
- Complexity of Finding Embeddings in a k-Tree
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs
- Parameterized Complexity of Elimination Distance to First-Order Logic Properties
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
- Hitting topological minors is FPT
- A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- A Faster Parameterized Algorithm for Treedepth
- Planarity Allowing Few Error Vertices in Linear Time
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- Parameterized and Exact Computation
- A Near-Optimal Planarization Algorithm
- Parameterized Algorithms
- \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
- Combing a Linkage in an Annulus
- k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
- Vertex deletion parameterized by elimination distance and even less
- On the Parameterized Complexity of Clique Elimination Distance
- Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
- Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes
- Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent
- Compound logics for modification problems
- Faster parameterized algorithms for modification problems to minor-closed classes
This page was built for publication: Faster parameterized algorithms for modification problems to minor-closed classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6601299)
