Kernels for packing and covering problems (Q2272393)

From MaRDI portal

Revision as of 18:40, 17 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Kernels for packing and covering problems	scientific article

Statements

scholarly article

0 references

Kernels for packing and covering problems (English)

0 references

0 references

Theoretical Computer Science

0 references

publication date

10 September 2019

0 references

zbMATH Keywords

combinatorial problems

0 references

packing

0 references

covering

0 references

kernelization

0 references

crown decomposition

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.tcs.2019.04.018

0 references

Graph-Theoretic Concepts in Computer Science

0 references

(Meta) Kernelization

0 references

Bidimensionality and Geometric Graphs

0 references

0 references

A Problem Kernelization for Graph Packing

0 references

On problems without polynomial kernels

0 references

Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size

0 references

Lower bounds for kernelizations and other preprocessing procedures

0 references

Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

0 references

AND-compression of NP-complete problems: streamlined proof and minor observations

0 references

Infeasibility of instance compression and succinct PCPs for NP

0 references

A kernelization algorithm for \(d\)-hitting set

0 references

An improved kernelization algorithm for \(r\)-set packing

0 references

Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths

0 references

Looking at the stars

0 references

An improved kernelization for \(P_{2}\)-packing

0 references

Kernelization for \(P_2\)-packing: a gerrymandering approach

0 references

Kernels for Packing and Covering Problems

0 references

Vertex and edge covers with clustering properties: Complexity and algorithms

0 references

On the parameterized complexity of vertex cover and edge cover with connectivity constraints

0 references

Parameterized complexity of finding subgraphs with hereditary properties.

0 references

Graph-Theoretic Concepts in Computer Science

0 references

Parameterized and Exact Computation

0 references

Crown reductions for the minimum weighted vertex cover problem

0 references

Vertex packings: Structural properties and algorithms

0 references

A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition

0 references

Crown structures for vertex cover kernelization

0 references

Fundamentals of parameterized complexity

0 references

Parameterized Algorithms

0 references

Maximum-Minimum Sätze über Graphen

0 references

Gallai-type theorems and domination parameters

0 references

Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem

0 references

Fixed-parameter tractability of graph modification problems for hereditary properties

0 references

A unified approximation algorithm for node-deletion problems

0 references

On bounded-degree vertex deletion parameterized by treewidth

0 references

Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

0 references

A Linear Kernel for Co-Path/Cycle Packing

0 references

Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems

0 references

On \(k\)-dependent domination

0 references

Parameterized complexity of finding regular induced subgraphs

0 references

On a generalization of Nemhauser and Trotter's local optimization theorem

0 references

A parameterized perspective on packing paths of length two

0 references

A faster parameterized algorithm for set packing

0 references

Matching and weighted \(P_2\)-packing: algorithms and kernels

0 references

Narrow sieves for parameterized paths and packings

0 references

Kernelization and Parameterized Algorithms for 3-Path Vertex Cover

0 references

A fixed-parameter algorithm for the vertex cover \(P_3\) problem

0 references

A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion

0 references

A faster FPT algorithm for 3-path vertex cover

0 references

Fixed-parameter algorithms for Vertex Cover \(P_3\)

0 references

Some results on graphs without long induced paths

0 references

The complexity of dissociation set problems in graphs

0 references

On a relation between \(k\)-path partition and \(k\)-path vertex cover

0 references

A fixed-parameter algorithm for the directed feedback vertex set problem

0 references

Parameterized Approximability of the Disjoint Cycle Problem

0 references

Algorithms - ESA 2003

0 references

A multivariate framework for weighted FPT algorithms

0 references

Crowns in bipartite graphs

0 references

Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps

0 references

Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion

0 references

A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem

0 references

A primal-dual approximation algorithm for the vertex cover \(P^3\) problem

0 references

On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique

0 references

Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs

0 references

Approximating Bounded Degree Deletion via Matroid Matching

0 references

Minimum \(k\)-path vertex cover

0 references

On the vertex \(k\)-path cover

0 references

Kernels for feedback arc set in tournaments

0 references

Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem

0 references

A \(2k\) kernel for the cluster editing problem

0 references

Efficient Parameterized Preprocessing for Cluster Editing

0 references

A more effective linear kernelization for cluster editing

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

10.1016/J.TCS.2019.04.018

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2272393

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2272393&oldid=38980227"