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

zbMATH Keywords

dynamic programmingparameterized complexitygraph minorspacking problemslinear kernelsprotrusion replacement

Mathematics Subject Classification ID

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)

Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Bidimensionality and Kernels ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

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