Polynomial kernels for hard problems on disk graphs

DOI10.1007/978-3-642-13731-0_30zbMATH Open1285.68123OpenAlexW1487121862MaRDI QIDQ3569901FDOQ3569901

Authors: Bart M. P. Jansen 

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13731-0_30

Recommendations

• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Linear problem kernels for planar graph problems with small distance property
• Planar graph vertex partition for linear problem kernels
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Tight kernel bounds for problems on graphs with small degeneracy

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (6)

• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
• Parameterized algorithms for stable matching with ties and incomplete lists
• Title not available (Why is that?)

This page was built for publication: Polynomial kernels for hard problems on disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569901)