| Paper title: |
Towards the Solution of NP Complete Problems |
| Published in: | Issue 3, (Vol. 4) / 2010 |
| Publishing date: | 2010-10-26 |
| Pages: | 63-66 |
| Author(s): | JINDAL Pawan , KUMAR Amit |
| Abstract. | The word algorithm is the magical word in the field of computer science because the imagination of the existence of any branch of computer science like artificial intelligence, computer network, human computer interaction etc. is useless without the word algorithm. There are some problems for which no any researcher is able to design those algorithms, which have polynomial time complexity in the worst case. No any researchers have even proved that no any polynomial time algorithm can solve them in worst case. NP complete problems arise in domains like automata and language theory, sequencing and scheduling, mathematical programming, algebra and number theory, games and puzzles, optimization problems, Boolean logic, graphs, arithmetic, designing of network, sets and partitions, storage and retrieval, biology, chemistry, physics etc. In this paper such kind of the problems (non deterministic polynomial type complete problem) is being studied along with the approximation algorithm for vertex cover problem. Researchers are applying their best efforts to design new approximation algorithms for nondeterministic polynomial type problems which have comparable less time complexity and space complexity as compared to the existing approximation algorithms. |
| Keywords: | Approximation Algorithms, NP Complete Problems. |
| References: | 1. E. Horowitz and S. Sahni, "Fundamental of Computer Algorithms", Computer Science Press,1982. 2. T. Cormen, C. Leiserson and R. Rivest, "Introduction to Algorithms", MIT Press, 1991 3. A.V. Aho, J.E. Hopcroft and J.D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974. 4. A.V. Aho, J.E. Hopcroft and J.D. Ullman, "Data Structures and Algorithms", Addison-Wesley,1984. 5. S. Baase, "Computer Algorithms: Introduction to Design and Analysis", Addison-Wesley 1988. 6. L. Banachowski, A. Kreczmar and W. Rytter, "Analysis of Algorithms and Data Structures",Addison-Wesley, 1991. 7. R. Baeza-Yates, "Teaching Algorithms", IV Iberoamerican Congress on Computer Science Education, Canela, Brazil, July 1995. 8. J. Nievergelt and K. Hinrichs, "Algorithms and Data Structures with Applications to Graphics and Geometry", Prentice-Hall, 1993. 9. G- Brassard, and P. Bratley, "Algorithmics: Theory and Practice", Prentice-Hall, 1988. 10. E.M. Reingold, J. Nievergelt and N. Deo, "Combinatorial Algorithms: Theory and Practice", Prentice-Hall, 1977. 11. H. Will, "Algorithms and Complexity", Prentice-Hall, 1986. 12. M. Crochemore and W. Rytter, "Text Algorithms", Oxford Press, 1994. 13. J.S. Vitter and P. Flajolet", "Average-case analysis of Algorithms and Data Structures", Handbook of Theoretical Computer Science (volume A), Elsevier and MIT Press, 1990, 431-524. 14. F.P. Preparata and M.I. Shamos. "Computational Geometry: An Introduction", Springer Verlag, 1985. 15. W. Frakes and R. Baeza-Yates, editors. "Information Retrieval: Data Structures and Algorithms",Prentice-Hall, 1992. 16. A. Gibbons and W. Rytter, "Efficient Parallel Algorithms", Cambridge University Press, 1988. 17. U. Manber, "Introduction to Algorithms: A Creative approach", Addison-Wesley, 1989. 18. G. Gonnet and R. Baeza-Yates, "Handbook of Algorithms and Data Structures", Addison- Wesley, 2ed, 1991. 19. Blaine A. Price, Ronald M. Beacker and Inn S. Small, A Principled Taxonomy of Software Visualization, Journal of Visual Languages and Computing 4, 211-266,. 20. B. Salzberg, "File Structures: An Analytic Approach", Prentice-Hall, 1988. 21. N. Wirth, "Algorithms and Data Structures" Prentice-Hall, 1986. 22. D. I-Iarel, "Algorithmics: The spirit of computing", AddisonWesley 1987. 23. Parberry, "Problems on Algorithms", Prentice-Hall, 1995. 24. P. Purdom and C. Brown, "The Analysis of Algorithms", Holt Reinhart and Winston, 1985. 25. M. Weiss, "Data Structures and Algorithm Analysis", Benjamin-Cummings, 1992. 26. D.E. Knuth, "The Art of Computer Programming", Vol. 3, "Sorting and Searching", Addison-Wesley, 1973. 27. D.C. Kozen, "The Design and Analysis of Algorithms", Springer-Verlag, 1992. 28. L. Kronsjo, "Algorithms: Their complexity and efficiency", John Wiley, 1979. 29. "An Introduction to Parallel Algorithms", Addison-Wesley, 1992. 30. F.T. Leighton, "Intr. to Parallel Algorithms and Architectures", Morgan Kaufmann, 1992. 31. H.R. Lewis and L. Denenberg, "Data Structures and Their Algorithms", Harper Collins Publishers, 1991. 32. M. J. Quinn, "Parallel Computing: Theory and Practice", McGraw-Hill, 1994. 33. S. Smith, "Design and Analysis of Algorithms", PWS-Kent, 1989. 34. N. Bansal, A. Blum, S. Chawla, and A. Meyerson, \Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time Windows," Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 166- 174, 2004. 35. B. Carr and S. Vempala, \Randomized meta-rounding," Random Structures and Algorithms, vol. 20(3), pp. 343-352, 2002. 36. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979. 37. R. Jothi and B. Raghavachari, \Approximating the k-Traveling Repairman Problem with Repairtimes," Journal of Discrete Algorithms, vol. 5, no. 2, pp. 293-303, 2007. 38. A. Blum, S. Chawla, D. R. Karger, T. Lane, A. Meyerson, and M. Minko®, \Approximation Algorithms for Orienteering and Discounted-Reward TSP," SIAM Journal on Computing, vol. 37, no. 2, pp. 653-670, 2007. |
| Back to the journal content | |
