TAILIEUCHUNG - Lecture Algorithm design - Chapter 10: Limits of tractability

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

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.