scientific article; zbMATH DE number 7053260
From MaRDI portal
Publication:5743379
zbMath1421.68078MaRDI QIDQ5743379
Daniel Lokshtanov, Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095123
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (14)
Characterising bounded expansion by neighbourhood complexity ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Editing to a Planar Graph of Given Degrees ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Combing a Linkage in an Annulus ⋮ Circumventing connectivity for kernelization ⋮ Unnamed Item ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Editing to a planar graph of given degrees ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Unnamed Item ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Linearity of grid minors in treewidth with applications through bidimensionality
- On problems without polynomial kernels
- A partial k-arboretum of graphs with bounded treewidth
- Graph minors. XVI: Excluding a non-planar graph
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Graph minors. XIII: The disjoint paths problem
- Contraction obstructions for treewidth
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Parametrized complexity theory.
- Local tree-width, excluded minors, and approximation algorithms
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Odd cycle packing
- Domination Problems in Nowhere-Dense Classes
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Tight Bounds for Linkages in Planar Graphs
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- The Induced Disjoint Paths Problem
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Spanners in Sparse Graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Polynomial-time data reduction for dominating set
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor
- A Separator Theorem for Nonplanar Graphs
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- A simpler algorithm and shorter proof for the graph minor decomposition
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
This page was built for publication:
