A refined search tree technique for dominating set on planar graphs

DOI10.1016/j.jcss.2004.03.007zbMath1101.68712OpenAlexW2075457919WikidataQ57359997 ScholiaQ57359997MaRDI QIDQ2575830

Ulrike Stege, Michael R. Fellows, Henning Fernau, Fran Rosamond, Rolf Niedermeier, Jochen Alber, Hong Bing Fan

Publication date: 7 December 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.03.007

zbMATH Keywords

NP-complete problemDominating setPlanar graphExact algorithmFixed-parameter tractabilitySearch tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Multistage graph problems on a global budget, A top-down approach to search-trees: Improved algorithmics for 3-hitting set, Genus characterizes the complexity of certain graph problems: Some tight results, Experiments on data reduction for optimal domination in networks, Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs, Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems, A strengthened analysis of an algorithm for dominating set in planar graphs, Guard games on graphs: keep the intruder out!, Implicit branching and parameterized partial cover problems, An Experimental Study on Generating Planar Graphs, Linearity of grid minors in treewidth with applications through bidimensionality, On complexities of minus domination, Improved algorithms and complexity results for power domination in graphs, Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles, R<scp>OMAN DOMINATION</scp>: a parameterized perspective†, A bounded search tree algorithm for parameterized face cover, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor, Linear time algorithms for finding a dominating set of fixed size in degenerated graphs

Cites Work

• A general method to speed up fixed-parameter-tractable algorithms
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph separators: A parameterized view
• Vertex Cover: Further Observations and Further Improvements
• A threshold of ln n for approximating set cover
• Polynomial-time data reduction for dominating set
• Approximation algorithms for NP-complete problems on planar graphs
• On efficient fixed-parameter algorithms for weighted vertex cover
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Parameterized complexity: exponential speed-up for planar graph problems
• STACS 2004
• Algorithms - ESA 2003
• LATIN 2004: Theoretical Informatics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item