|
ANALYSIS OF ALGORITHMS
(0368.4222.01)
Lecturer: Uri Zwick
|
|
Minimum Spanning Trees
Classical deterministic algorithms (Kruskal, Prim, Borůvka)
More efficient algorithms (Yao, Fredman-Tarjan)
|
Presentation (pptx)
|
|
Minimum Spanning Trees
Verification
Linear time verification algorithm
(Komlós, King, Hagerup)
Checking meldable heaps (Bright-Sullivan)
LCA queries (Bender-Farach Colton)
Range Maxima (Vuillemin)
|
Presentation (pptx)
|
|
Minimum Spanning Trees
Randomized linear time algorithm (Karger-Klein-Tarjan)
|
Presentation (pptx)
|
|
Minimum Directed Spanning
Trees
Edmonds’ algorithm (Chin-Liu,
Edmonds, Bock)
Efficient implementations (Tarjan, Gabow-Galil-Sepncer-Tarjan)
|
Presentation (pptx)
|
|
Shortest Paths
Goldberg's scaling algorithm
|
Presentation (pptx)
|
|
Minimum Mean Weight Cycles
Karp’s algorithm
|
Presentation (pptx)
|
|
Min Cost Flow
A strongly polynomial time
algorithm
|
Presentation (pptx)
Lecture Notes (pdf)
|
|
Maximum non-bipartite
matching
Edmonds' blossom shrinking
algorithm
Efficient implementation
|
Presentation (pptx)
|
|
Maximum weighted
non-bipartite matching
|
Presentation (pptx)
|