Tutorial — Optimal Station Frequencies

Với một trạm $v$ bất kỳ khi các trạm lân cận đã được gán giá trị, hàm tổng khoảng cách là một hàm lồi theo biến $a_v$ trên đoạn $[l_v, r_v]$. Giá trị lớn nhất của hàm lồi trên một đoạn đóng luôn đạt được tại hai đầu mút, do đó ta chỉ cần quan tâm đến hai khả năng $a_v = l_v$ hoặc $a_v = r_v$ cho mỗi trạm.

Vì đồ thị liên lạc là một cây không chứa chu trình, cấu hình tối ưu của một cây con chỉ phụ thuộc vào việc đỉnh gốc của cây con đó chọn giá trị ở biên trái hay biên phải. Khi cố định giá trị tần số của một đỉnh, các nhánh cây con nối với các đỉnh con của nó hoàn toàn độc lập với nhau.

Áp dụng phương pháp quy hoạch động trên cây với hai trạng thái tại mỗi đỉnh $u$: $dp(u, 0)$ ứng với $a_u = l_u$ và $dp(u, 1)$ ứng với $a_u = r_u$. Ta duyệt các đỉnh theo thứ tự topo từ lá lên gốc bằng thuật toán duyệt theo chiều rộng đảo ngược để cập nhật kết quả từ các đỉnh con lên đỉnh cha một cách an toàn và tránh tràn ngăn xếp.