Vertex Cover: Further Observations and Further Improvements
作者： Jianer Chen , Iyad A. Kanj , Weijia Jia
关键词:
摘要: … In the present paper, we develop a further improved … of k vertices, we essentially only need to concentrate on graphs of at … degree at most 5, so we do not need to further branch at it. …
springer.com
researchgate.net 
sci-hub.st 参考文章(25)
Dorit S. Hochbaum, Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems Approximation algorithms for NP-hard problems. pp. 94- 143 ,(1996)
Rodney G. Downey, Michael R. Fellows, Ulrike Stege, Parameterized complexity: A framework for systematically confronting computational intractability. Contemporary Trends in Discrete Mathematics. pp. 49- 100 ,(1997)
Ulrike Stege, Michael Ralph Fellows, None, An improved fixed parameter tractable algorithm for vertex cover Technical report / Departement Informatik, ETH Zürich. ,vol. 318, ,(1999) , 10.3929/ETHZ-A-006653305
R. Bar-Yehuda, S. Even, A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem workshop on graph-theoretic concepts in computer science. ,vol. 109, pp. 27- 45 ,(1985) , 10.1016/S0304-0208(08)73101-3
Rodney G. Downey, Michael R. Fellows, Parameterized Computational Feasibility Birkhäuser Boston. pp. 219- 244 ,(1995) , 10.1007/978-1-4612-2566-9_7
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning, Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search international colloquium on automata, languages and programming. pp. 236- 247 ,(2000) , 10.1007/3-540-45022-X_21
Tang Jian, An O(2 0.304n ) Algorithm for Solving Maximum Independent Set Problem IEEE Transactions on Computers. ,vol. 35, pp. 847- 851 ,(1986) , 10.1109/TC.1986.1676847
R. Balasubramanian, Michael R. Fellows, Venkatesh Raman, An improved fixed-parameter algorithm for vertex cover Information Processing Letters. ,vol. 65, pp. 163- 168 ,(1998) , 10.1016/S0020-0190(97)00213-5
Rolf Niedermeier, Peter Rossmanith, A general method to speed up fixed-parameter-tractable algorithms Information Processing Letters. ,vol. 73, pp. 125- 129 ,(2000) , 10.1016/S0020-0190(00)00004-1
Jonathan F. Buss, Judy Goldsmith, Nondeterminism within P SIAM Journal on Computing. ,vol. 22, pp. 560- 572 ,(1993) , 10.1137/0222038