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

Nguyễn Ngọc Trung

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.

 

 


Từ khóa


đồ thị khoảng đều; thuật toán tham lam; các bài toán tối ưu

Toàn văn:

PDF (English)

Trích dẫn


Chang, M. (1998). Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM Journal of Computing, 27(6), 1671-1694.

Heggernes, P., Lokshtanov, D., Mihai, R., & Papadopoulos, C. (2008). Cutwidth of split graphs, threshold graphs, and proper interval graphs. Proceedings of WG 2008, Lecture Notes in Computer Science, 5344, 218-229.

Hsu, W., & Tsai, K. H. (1991). Linear time algorithms on circular-arc graphs.

Information Processing Letters, 40(3), 123-129.

Van Leeuwen, E. J., (2005). Approximation Algorithms for Unit Disk Graphs. In: Kratsch D. (eds) Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, 3787, 351-361.

Yuan, J., & Zhou, S., (1995). Optimal labelling of unit interval graphs. Applied Mathematics-a Journal of Chinese Universities Series B, 10, 337-344.




DOI: https://doi.org/10.54607/hcmue.js.17.3.2634(2020)

Tình trạng

  • Danh sách trống