Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Lecture Algorithm design - Chapter 10: Limits of tractability include all of the following: Finding small vertex covers, solving NP-hard problems on trees, circular arc coverings, vertex cover in bipartite graphs. | Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley http www.cs.princeton.edu wayne kleinberg-tardos 10. Extending Tractability finding small vertex covers solving NP-hard problems on trees circular arc coverings vertex cover in bipartite graphs Last updated on 11 3 15 5 43 AM Coping with NP-completeness Q. Suppose I need to solve an NP-complete problem. What should I do A. Theory says you re unlikely to find poly-time algorithm. Must sacrifice one of three desired features. Solve problem to optimality. Solve problem in polynomial time. Solve arbitrary instances of the problem. This lecture. Solve some special cases of NP-complete problems. 2 10. Extending Tractability finding small vertex covers solving NP-hard problems on trees circular arc coverings vertex cover in bipartite .
