Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
DOI10.1137/18M1228839zbMath1461.05164arXiv1609.07780OpenAlexW3121848388MaRDI QIDQ5150814
Marcin Wrochna, Dimitrios M. Thilikos, Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond
Publication date: 15 February 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1609.07780
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- Effective computation of immersion obstructions for unions of graph classes
- A minimum degree condition forcing complete graph immersion
- The structure of graphs not admitting a fixed immersion
- Graph minors. XX: Wagner's conjecture
- On an edge ranking problem of trees and graphs
- Parameterized graph separation problems
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Graph minors. V. Excluding a planar graph
- Call routing and the ratcatcher
- Edge ranking of graphs is hard
- An FPT 2-approximation for tree-cut decomposition
- An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
- Graph minors. XIII: The disjoint paths problem
- Minors in graphs of large \(\theta_r\)-girth
- Packing and covering immersion-expansions of planar sub-cubic graphs
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A Structure Theorem for Strong Immersions
- Excluded Grid Theorem
- Algorithmic Applications of Tree-Cut Width
- Polynomial Bounds for the Grid-Minor Theorem
- (Meta) Kernelization
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Easy problems for tree-decomposable graphs
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- Fast Algorithms forK4Immersion Testing
- Complete graph immersions and minimum degree
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Immersions in Highly Edge Connected Graphs
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- Finding topological subgraphs is fixed-parameter tractable
- Cutwidth I: A linear time fixed parameter algorithm
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A weak immersion relation on graphs and its applications
This page was built for publication: Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
