Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
From MaRDI portal
Publication:4554933
DOI10.1145/3108239zbMATH Open1451.68137arXiv1305.4914OpenAlexW2153676433MaRDI QIDQ4554933
Author name not available (Why is that?)
Publication date: 12 November 2018
Published in: (Search for Journal in Brave)
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 . 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.
Full work available at URL: https://arxiv.org/abs/1305.4914
No records found.
No records found.
This page was built for publication: Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554933)
