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 Thành phố Hồ Chí Minh , 2020

Mô tả vật lý:

Bộ sưu tập: Metadata

ID: 394308

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., Tóm tắt tiếng anh, In this paper, we show a very special property of unit interval graphs and use that property to introduce greedy algorithms for classical optimization problems on them: finding minimum dominating set, maximum independent set and maximum matching. These algorithms are all linear-time concerning the number of vertices of the graph and simple for implementation.

1.

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