scientific article; zbMATH DE number 2089218

MaRDI QIDQ3046487zbMATH OpenFDO

Authors Jochen Alber, Michael R. Fellows, Rolf Niedermeier

Publication date 12 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2368/23680150.htm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Polynomial-time data reduction for dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Linear Kernel for Planar Connected Dominating Set

Cited in

(10)

• Graph separators: A parameterized view
• Simpler linear-time kernelization for planar dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• An experimental study on generating planar graphs
• Polynomial-time data reduction for dominating set
• A linear kernel for planar red-blue dominating set
• A linear kernel for a planar connected dominating set
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• Experiments on data reduction for optimal domination in networks

This page was built for publication:

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