intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

On the performance of a simple approximation algorithm for the longest path problem

Chia sẻ: ViNaruto2711 ViNaruto2711 | Ngày: | Loại File: PDF | Số trang:12

40
lượt xem
0
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

The longest path problem is known to be NP-hard. Moreover, it cannot be approximated within a constant ratio, unless P = NP. The best known polynomial time approximation algorithms for this problem essentially find a path of length that is the logarithm of the optimum.

Chủ đề:
Lưu

Nội dung Text: On the performance of a simple approximation algorithm for the longest path problem

ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2