RÚT GỌN ĐỒ THỊ CHO BÀI TOÁN CÂY STEINER NHỎ NHẤT

Phan Tân Quốc



DOI: 10.15625/vap.2016.00079

Abstract


Cây Steiner nhỏ nhất (Steiner Minimal Tree - SMT) là bài toán tối ưu tổ hợp có nhiều ứng dụng quan trọng trong khoa học và kỹ thuật; đây là bài toán thuộc lớp NP-hard và hiện đang được nghiên cứu rộng rãi. Các tiếp cận giải bài toán SMT - dù là giải đúng hay giải gần đúng - thì công đoạn rút gọn đồ thị là rất quan trọng; công đoạn này càng có ý nghĩa đối với các tiếp cận giải đúng bài toán SMT. Trong hàng chục năm qua, đã có hàng loạt thuật toán rút gọn đồ thị cho bài toán SMT đã được công bố; các kết quả này đã hỗ trợ tích cực cho việc giải bài toán SMT với kích thước lớn hơn. Bài báo này đề xuất thuật toán rút gọn đồ thị cho bài toán SMT và kết quả thực nghiệm là thông tin hữu ích cho việc nghiên cứu các thuật toán giải đúng cũng như các thuật toán giải gần đúng cho bài toán SMT.

Keywords


Steiner minimal tree, graph reduction, branch and bound algorithm, exact algorithms for steiner minimal tree



Copyright (c) 2017 PROCEEDING of Publishing House for Science and Technology



PROCEEDING

PUBLISHING HOUSE FOR SCIENCE AND TECHNOLOGY

Website: http://vap.ac.vn

Contact: nxb@vap.ac.vn