Sort:
Open Access Issue
Dynamic Dominating Set and Turbo-Charging Greedy Heuristics
Tsinghua Science and Technology 2014, 19(4): 329-337
Published: 30 July 2014
Abstract PDF (828.1 KB) Collect
Downloads:58

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.

Open Access Issue
Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen
Tsinghua Science and Technology 2014, 19(4): 325-328
Published: 30 July 2014
Abstract PDF (587.3 KB) Collect
Downloads:68

This short paper highlights some open problems related to the work of Jianer Chen in the area of parameterized/multivariate algorithmics.

Total 2