On the parameterized complexity of dynamic problems

DOI10.1016/J.TCS.2015.06.053MaRDI QIDQ896122zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.06.053

zbMATH Keywords

parameterized complexitydynamic problemsre-optimizationdynamic connected dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On the parameterized complexity of dynamic problems with connectivity constraints
• Dynamic Parameterized Problems
• Dynamic parameterized problems
• Parameterized dynamic variants of red-blue dominating set
• Fast dynamic graph algorithms for parameterized problems

Cites work

• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A theory and algorithms for combinatorial reoptimization
• An exact algorithm for connected red-blue dominating set
• Dynamic dominating set and turbo-charging greedy heuristics
• Dynamic vehicle routing: Status and prospects
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Incremental list coloring of graphs, parameterized by conservation
• Monads for incremental computing
• Reoptimization of Steiner trees: changing the terminal set

Cited in

(15)

• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Parameterized Dynamic Cluster Editing
• Multistage graph problems on a global budget
• On the parameterized complexity of dynamic problems with connectivity constraints
• Parameterized dynamic variants of red-blue dominating set
• Parameterized Complexity of DPLL Search Procedures
• Reoptimization of parameterized problems
• Dynamic parameterized problems
• Dynamic parameterized problems and algorithms
• Fast dynamic graph algorithms for parameterized problems
• A theory and algorithms for combinatorial reoptimization
• Multistage vertex cover
• Dynamic dominating set and turbo-charging greedy heuristics
• Parameterized dynamic cluster editing
• Dynamic Parameterized Problems

This page was built for publication: On the parameterized complexity of dynamic problems

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