Polynomial kernels for hard problems on disk graphs

DOI10.1007/978-3-642-13731-0_30MaRDI QIDQ3569901zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(6)

• 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
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs

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)