Improved Parameterized Upper Bounds for Vertex Cover

1. Balasubramanian, R., Fellows, M., Raman, V.: An improved fixed parameter algorithm for Vertex Cover. Information Processing Letters 65, 163–168 (1998)

   Article  MathSciNet  Google Scholar 

2. Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the Weighted Vertex Cover problem. Annals of Discrete Mathematics 25, 27–46 (1985)

   MathSciNet  Google Scholar 

3. Buss, J., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing 22, 560–572 (1993)

   Article  MATH  MathSciNet  Google Scholar 

4. Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences 67(4), 789–807 (2003)

   Article  MATH  MathSciNet  Google Scholar 

5. Sunil Chandran, L., Grandoni, F.: Refined memorisation for vertex cover. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 61–70. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

6. Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.: Solving large FPT problems on coarse grained parallel machines. Journal of Computer and System Sciences 67(4), 691–706 (2003)

   Article  MATH  MathSciNet  Google Scholar 

7. Chen, J., Kanj, I., Jia, W.: Vertex cover: further observations and further improvements. Journal of Algorithms 41, 280–301 (2001)

   Article  MATH  MathSciNet  Google Scholar 

8. Chen, J., Liu, L., Jia, W.: Improvement on Vertex Cover for low degree graphs. Networks 35, 253–259 (2000)

   Article  MATH  MathSciNet  Google Scholar 

9. Chlebik, M., Chlebikova, J.: Crown reductions for the minimum weighted vertex cover problem. Electronic Colloquium on Computational Complexity, Report No. 101 (2004)

   Google Scholar 

10. Downey, R., Fellows, M.: Fixed-parameter tractability and completeness. Congressus Numerantium 87, 161–187 (1992)

    MathSciNet  Google Scholar 

11. Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)

    Google Scholar 

12. Ebengger, C., Hammer, P., de Werra, D.: Pseudo-boolean functions and stability of graphs. Annals of Discrete Mathematics 19, 83–98 (1984)

    Google Scholar 

13. Fellows, M.R.: Blow-ups, win/Win’s, and crown rules: Some new directions in FPT. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 1–12. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

14. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)

    MATH  Google Scholar 

15. Impagliazzo, R., Paturi, R.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63, 512–530 (2001)

    Article  MATH  MathSciNet  Google Scholar 

16. Nemhauser, G., Trotter, L.: Vertex packing: structural properties and algorithms. Mathematical Programming 8, 232–248 (1975)

    Article  MATH  MathSciNet  Google Scholar 

17. Niedermeier, R., Rossmanith, P.: Upper bounds for Vertex Cover further improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 561–570. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

18. Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. Journal of Algorithms 47, 63–77 (2003)

    MATH  MathSciNet  Google Scholar 

19. Robson, J.M.: Algorithms for maximum independent set. Journal of Algorithms 6, 425–440 (1977)

    MathSciNet  Google Scholar 

20. Stege, U., Fellows, M.: An improved fixed-parameter-tractable algorithm for Vertex Cover. Technical Report 318, Department of Computer Science, ETH Zürich (April 1999)

    Google Scholar 

Download references