Explicit linear kernels for packing problems
DOI10.1007/s00453-018-0495-5zbMath1422.68111arXiv1610.06131OpenAlexW2538886279WikidataQ129341636 ScholiaQ129341636MaRDI QIDQ1739112
Ignasi Sau, Valentin Garnero, Dimitrios M. Thilikos, Christophe Paul
Publication date: 25 April 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.06131
dynamic programmingparameterized complexitygraph minorspacking problemslinear kernelsprotrusion replacement
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Scattered packings of cycles
- Irrelevant vertices for the planar disjoint paths problem
- Graph-based data clustering with overlaps
- Kernel bounds for disjoint cycles and disjoint paths
- Faster parameterized algorithms for minor containment
- Explicit bounds for graph minors
- Linearity of grid minors in treewidth with applications through bidimensionality
- Graph minors. V. Excluding a planar graph
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Treewidth. Computations and approximations
- On search, decision, and the efficiency of polynomial-time algorithms
- Graph minors. XVI: Excluding a non-planar graph
- Reduction algorithms for graphs of small treewidth
- Graph minors. XIII: The disjoint paths problem
- Contraction obstructions for treewidth
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Kernelization Algorithms for Packing Problems Allowing Overlaps
- Strengthening Erdös-Pósa property for minor-closed graph classes
- (Meta) Kernelization
- Explicit Linear Kernels via Dynamic Programming
- Weak Second‐Order Arithmetic and Finite Automata
- Polynomial-time data reduction for dominating set
- A Problem Kernelization for Graph Packing
- An algebraic theory of graph reduction
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- A Parameterized Algorithm for Packing Overlapping Subgraphs
- Polynomial bounds for the grid-minor theorem
- On Independent Circuits Contained in a Graph
- Bidimensionality and Geometric Graphs
- A simpler algorithm and shorter proof for the graph minor decomposition
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Large-treewidth graph decompositions and applications
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The ${\mathcal{G}}$ -Packing with t-Overlap Problem
This page was built for publication: Explicit linear kernels for packing problems