MỘT SỐ THUẬT TOÁN THAM LAM CHO CÁC BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ KHOẢNG ĐỀU

Tóm tắt

Trong bài báo này, chúng tôi chỉ ra một tính chất rất đặc biệt của đồ thị khoảng đều và sử dụng nó để đề xuất một số thuật toán tham lam cho các bài toán tối ưu cổ điển trên lớp đồ thị này bao gồm: tìm tập đỉnh bao quát nhỏ nhất, tìm tập đỉnh độc lập lớn nhất và tìm một cách ghép đôi lớn nhất. Các thuật toán này đều có độ phức tạp tuyến tính theo số đỉnh của đồ thị và có thể được lập trình dễ dàng.