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:15

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:19

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

Total 2