Một số thuật toán tham lam cho các bài toán tối ưu trên đồ thị khoảng đều.

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Ngọc Trung Nguyễn

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học (Trường Đại học Sư phạm TP. Hồ Chí Minh), 2020

Mô tả vật lý: 547-554

Bộ sưu tập: Metadata

ID: 426480

Thêm vào giỏ Liên kết toàn văn

Tóm tắt
Chủ đề

Trong bài báo này, chúng tôi chỉ ra một tính chất rất đặc biệt của đồ thị khoảng đều và sử dụng nó để đề xuất một số thuật toán tham lam cho các bài toán tối ưu cổ điển trên lớp đồ thị này bao gồm tìm tập đỉnh bao quát nhỏ nhất, tìm tập đỉnh độc lập lớn nhất và tìm một cách ghép đôi lớn nhất. Các thuật toán này đều có độ phức tạp tuyến tính theo số đỉnh của đồ thị và có thể được lập trình dễ dàng.

Tạo bộ sưu tập với mã QR