Parameterized dynamic variants of red-blue dominating set

DOI10.1007/978-3-030-38919-2_20MaRDI QIDQ3297772zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam, Henning Fernau, Cristina Bazgan

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://basepub.dauphine.psl.eu/handle/123456789/22263

zbMATH Keywords

dynamic problemshitting setparameterized complexityreoptimizationset cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• On the parameterized complexity of dynamic problems
• On the parameterized complexity of dynamic problems with connectivity constraints
• Dynamic dominating set and turbo-charging greedy heuristics
• A linear kernel for planar red-blue dominating set
• An exact algorithm for connected red-blue dominating set

Cites work

• A survey on alliances and related parameters in graphs
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Capacitated Domination and Covering: A Parameterized Perspective
• Capacitated domination: problem complexity and approximation algorithms
• Computing small partial coverings
• Dynamic dominating set and turbo-charging greedy heuristics
• Dynamic parameterized problems and algorithms
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Integer Programming with a Fixed Number of Variables
• LIMITS and applications of group algebras for parameterized problems
• On problems as hard as CNF-SAT
• On the Hardness of Reoptimization
• On the parameterized complexity of dynamic problems
• Parameterizations of hitting set of bundles and inverse scope
• Planar capacitated dominating set is \(W[1]\)-hard
• Reoptimization of set covering problems
• Reoptimization of Weighted Graph and Covering Problems
• The parameterized complexity of k-biclique
• The parameterized complexity of the k-biclique problem
• The Turing way to parameterized complexity

Cited in

(5)

• Structural parameterizations of dominating set variants
• When is red-blue nonblocker fixed-parameter tractable?
• On the parameterized complexity of dynamic problems with connectivity constraints
• Dynamic dominating set and turbo-charging greedy heuristics
• On the parameterized complexity of dynamic problems

This page was built for publication: Parameterized dynamic variants of red-blue dominating set

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