Giải thuật cho bài toán vị trí lát cắt tổng tối tiểu trên đồ thị

Abstract

Bài báo này nghiên cứu vấn đề tìm một lát cắt phân chia một đồ thị liên thông thành hai thành phần liên thông rời nhau sao cho tổng khoảng cách có trọng số từ bất kỳ đỉnh nào của đồ thị đến lát cắt là nhỏ nhất. Bài toán này được gọi là bài toán lát cắt tổng tối tiểu. Bài báo sẽ chứng minh rằng bài toán này là NP-khó trên đồ thị tổng quát bằng cách quy giản bài toán phủ tập hợp về bài toán này và đồng thời chỉ ra rằng bài toán trên đồ thị cây có thể giải trong thời gian tuyến tính bằng quy hoạch động.

Keywords

• Bài toán vị trí, lát cắt, trung vị, độ phức tạp, quy hoạch động