TAILIEUCHUNG - Skiena - The Algorithm Design Manual [Springer-Verlag 1997] Episode 5

Tham khảo tài liệu 'skiena - the algorithm design manual [springer-verlag 1997] episode 5', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Shortest Path Related Problems Network flow see page motion planning see page . Next Upl Previousl Contents 1 Index CD Home 1 Lecture Notes Algorithms Repository I Next Transitive Closure and Reduction Up Graph Problems Polynomial-Time Previous Minimum Spanning Tree Algorithms Mon Jun 2 23 33 50 EDT1997 file E BOOK BOOK4 5 of 5 19 1 2003 1 31 00 Transitive Closure and Reduction The simplest algorithm just performs a breadth-first or depth-first search from each vertex and keeps track of all vertices encountered. Doing n such traversals gives an O n n m algorithm which degenerates to cubic time if the graph is dense. This algorithm is easily implemented runs well on sparse graphs and is likely the right answer for your application. If the transitive closure of G will be dense a better algorithm exploits the fact that the strongly connected components of G can be computed in linear time see Section l l . All pairs of vertices in each strongly connected component are mutually reachable. Further if x y is an edge between two vertices in different strongly connected components every vertex in y s component is reachable from each vertex in x s component. Thus the problem reduces to finding the transitive closure on a graph of strongly connected components which should have considerably fewer edges and vertices than G. Warshall s algorithm constructs transitive closures in with a simple slick algorithm that is identical to Floyd s all-pairs-shortest-path algorithm of Section 1 1. If we are interested only in the transitive closure and not the length of the resulting paths we can reduce storage by retaining only one bit for each matrix element. Thus iff j is reachable from i using only vertices as intermediates. Another related algorithm discussed in the references runs in the same time as matrix multiplication. You might conceivably win for large n by using Strassen s fast matrix multiplication algorithm although I for one wouldn t bother trying. Since .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.