arxiv: 1305.4914 · v2 · pith:2Q572O2Onew · submitted 2013-05-21 · 💻 cs.DS

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

Marek Cygan , Fabrizio Grandoni , Danny Hermelin This is my paper

classification 💻 cs.DS

keywords graphskernelizationproblemsboundsd-degeneratefreeknowntight

0 comments p. Extension

Add this Pith Number to your LaTeX paper

\usepackage{pith}
\pithnumber{2Q572O2O}

Prints a linked pith:2Q572O2O badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

read the original abstract

In this paper we consider kernelization for problems on d-degenerate graphs, i.e. graphs such that any subgraph contains a vertex of degree at most $d$. This graph class generalizes many classes of graphs for which effective kernelization is known to exist, e.g. planar graphs, H-minor free graphs, and H-topological-minor free graphs. We show that for several natural problems on d-degenerate graphs the best known kernelization upper bounds are essentially tight.

This paper has not been read by Pith yet.

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

discussion (0)