Linear Kernel for Planar Connected Dominating Set

DOI10.1007/978-3-642-02017-9_31MaRDI QIDQ3630213zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Matthias Mnich, Saket Saurabh

Publication date 3 June 2009

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-02017-9_31

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05)

Recommendations

• A linear kernel for planar total dominating set
• Improved linear problem kernel for planar connected dominating set
• A linear kernel for planar red-blue dominating set
• scientific article; zbMATH DE number 6678911
• An improved kernel for planar connected dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Simpler linear-time kernelization for planar dominating set
• A Linear Kernel for Planar Feedback Vertex Set

Cited in

(20)

• Simpler linear-time kernelization for planar dominating set
• An improved kernel for planar connected dominating set
• scientific article; zbMATH DE number 2089218 (Why is no real title available?)
• New analysis and computational study for the planar connected dominating set problem
• Bidimensionality and kernels
• Planar graph vertex partition for linear problem kernels
• Connectivity is not a limit for kernelization: planar connected dominating set
• Polynomial-time data reduction for dominating set
• Kernelization: new upper and lower bound techniques
• Improved linear problem kernel for planar connected dominating set
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• A linear kernel for planar total dominating set
• The kernelization complexity of connected domination in graphs with (no) small cycles
• A Retrospective on (Meta) Kernelization
• A linear kernel for planar red-blue dominating set
• A linear kernel for a planar connected dominating set
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• On parameterized independent feedback vertex set

This page was built for publication: Linear Kernel for Planar Connected Dominating Set

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