Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

导出

摘要 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.

作者 Rodney G.Downey Judith Egan Michael R.Fellows Frances A.Rosamond Peter Shaw

机构地区 School of Mathematics School of Engineering and Information Technology

出处《Tsinghua Science and Technology》 SCIE EI CAS 2014年第4期329-337,共9页 清华大学学报（自然科学版（英文版）

基金 supported by the Australian Research Council

关键词 kernelization multivariate algorithms parameterized algorithms turbo-charging heuristics kernelization multivariate algorithms parameterized algorithms turbo-charging heuristics

分类号 TK40 [动力工程及工程热物理—动力机械及工程] TP13 [自动化与计算机技术—控制理论与控制工程]

引文网络
相关文献

参考文献30

1R.M.Karp,Heuristic algorithms in computational molecular biology,J.Comput.Syst.Sci.,vol.77,no.1,pp.122-128,2011.
2L.Cai,J.Chen,R.G.Downey,and M.R.Fellows,On the structure of parameterized problems in NP,Inf Comput.,vol.123,no.1,pp.38-49,1995.
3L.Cai,J.Chen,R.G.Downey,and M.R.Fellows,Advice classes of parameterized tractability,Ann.Pure Appl.Logic,vol.84,no.l,pp.119-138,1997.
4L.Cai,J.Chen,R.G.Downey,and M.R.Fellows,On the parameterized complexity of short computation and factorization,Arch.Math.Log.,vol.36,nos.4-5,pp.321-337,1997.
5J.Chen,Randomized disposal of unknowns and implicitly enforced bounds on parameters,in IWPEC,2008,pp.1-8.
6J.Chen,Vertex cover kernelization,in Encyclopedia of Algorithms,M.Y.Kao,ed.Springer,2008.
7J.Chen,Maximum partition matching,in Encyclopedia of Opti-Mization.Kluwer Academic Publishers,2009,pp.2029-2035.
8J.Chen and S.B.Cooper,Algorithms,complexity and computational models,Theor.Comput.Sci.,vol.412,no.23,pp.2457-2458,2011.
9J.Chen,H.Fernau,I.A.Kanj,and G.Xia,Parametric duality and kernelization:Lower bounds and upper bounds on kernel size,in STACS,2005,pp.269-280.
10J.Chen and I.A.Kanj,Parameterized complexity and subexponential-time computability,in The Multivariate Algorithmic Revolution and Beyond,2012,pp.162-195.

1王元璋.部分Broyden方法及其对离散fpT方程组的应用[J].计算物理,1990,7(2):228-234.
2侯爱华,陈蛇,曾鹦,李元桢.城市公交FPT模式的人因社会模型探析[J].未来与发展,2016,37(8):67-73.
3单而芳,康丽英.On the dominating set in circular arc graphs[J].西安电子科技大学学报,1996,23(S1):126-129.
4车模卖场[J].汽车杂志,2009(9):308-309.
5孙良.ON THREE CONJECTURES OF B. ZELINKA IN GRAPH THEORY[J].Chinese Science Bulletin,1988,33(12):969-970.
6CHENYaojun,ZHANGYunqing,ZHANGKemin.IS γα≤δ FOR GRAPHS WHICH HAVE DIAMETER TWO?[J].Journal of Systems Science & Complexity,2003,16(2):195-198.
7配备伊顿机械增压器的沃尔沃发动机获年度发动机大奖[J].汽车与配件,2015,0(24):20-20.
8张艽,田泽荣.多元多项式乘积的多项式变换算法[J].湖南文理学院学报（自然科学版）,2006,18(1):17-18.
9田京京.汉水上游生态城市交通信号灯和交警岗点设置研究——以汉台区中心城区为例[J].科技和产业,2013,13(7):130-132.
10法国国营铁路电子控制集中装置的要求[J].中国铁路,2011(8):81-81.

Tsinghua Science and Technology

2014年第4期

浏览历史

内容加载中请稍等...

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

参考文献30

相关作者

相关机构

相关主题

浏览历史