The main purpose of this paper is to exposit two very different,but very general,motivational schemes in the art of parameterization and a concrete example connecting them.We introduce a dynamic version of the DOMINAT...The main purpose of this paper is to exposit two very different,but very general,motivational schemes in the art of parameterization and a concrete example connecting them.We introduce a dynamic version of the DOMINATING SET problem and prove that it is fixed-parameter tractable(FPT).The problem is motivated by settings where problem instances evolve.It also arises in the quest to improve a natural greedy heuristic for the DOMINATING SET problem.展开更多
文摘The main purpose of this paper is to exposit two very different,but very general,motivational schemes in the art of parameterization and a concrete example connecting them.We introduce a dynamic version of the DOMINATING SET problem and prove that it is fixed-parameter tractable(FPT).The problem is motivated by settings where problem instances evolve.It also arises in the quest to improve a natural greedy heuristic for the DOMINATING SET problem.
