Việc đóng cửa chuyển tiếp của biểu đồ được xác định e. g. ở đây: http://mathworld.wolfram.com/TransitiveClosure.htmlThời gian chạy Asymtotic cần thiết để tính toán đóng cửa chuyển tiếp của biểu đồ?
Có thể dễ dàng trong O (n^3), trong đó n là số đỉnh. Tôi đã tự hỏi nếu nó có thể được thực hiện trong thời gian O (n^2).
Không. Tôi không nghĩ rằng có một thuật toán O (n) cho nó. Tôi mong đợi nếu như một thuật toán tồn tại, bạn có thể giải quyết tất cả các cặp đường đi ngắn nhất vấn đề trong O (n) quá, đó không phải là trường hợp. Thuật toán nhanh nhất tiệm cận tôi có thể nghĩ là triển khai thuật toán đường đi ngắn nhất của Dijkstra với một dải Fibonacci (O (n log n) trong các đồ thị không dày đặc).
Hmm. Tôi tìm thấy một thuật toán tính toán đóng cửa chuyển tiếp trong thời gian chạy O (n^2) EXPECTED.
Cho rằng đây:
Bạn có thể đưa ra một O (kn^2 + m) đóng bắc cầu/giảm thuật toán, với k là số mất tích/cạnh bổ sung trong việc đóng cửa bắc cầu /giảm?
Vẫn được coi là câu hỏi mở bởi những người nghĩ về những điều này nhiều hơn chúng tôi, tôi muốn nói "Tôi không biết".
(Nhưng nếu bạn giải quyết nó và muốn có một tiến sĩ, tôi biết rằng thuật toán.)
mà phân phối ngẫu nhiên? – jpalecek
không có ý tưởng. tôi không muốn sử dụng nó, bởi vì tôi không muốn bất kỳ sự ngẫu nhiên nào trong thuật toán xung quanh của mình. nó ở đây: http://www.springerlink.com/content/f511w61n62l17168/ – nes1983