On the parameterized complexity of dynamic problems

DOI10.1016/j.tcs.2015.06.053zbMath1333.68130OpenAlexW815725825MaRDI QIDQ896122

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

dynamic problemsparameterized complexityre-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)

Related Items (9)

Multistage graph problems on a global budget ⋮ Multistage vertex cover ⋮ Reoptimization of parameterized problems ⋮ A theory and algorithms for combinatorial reoptimization ⋮ Parameterized dynamic cluster editing ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Dynamic parameterized problems ⋮ Parameterized Dynamic Cluster Editing ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Incremental list coloring of graphs, parameterized by conservation
• An exact algorithm for connected red-blue dominating set
• Reoptimization of Steiner trees: changing the terminal set
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Dynamic vehicle routing: Status and prospects
• A Theory and Algorithms for Combinatorial Reoptimization
• Monads for incremental computing
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems

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