Premium
Finding optimum branchings
Author(s) -
Tarjan R. E.
Publication year - 1977
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230070103
Subject(s) - combinatorics , graph , mathematics , running time , branching (polymer chemistry) , discrete mathematics , algorithm , computer science , materials science , composite material
Chu and Liu, Edmonds, and Bock have independently devised an efficient algorithm to find an optimum branching in a directed graph. We give an implementation of the algorithm which runs in 0(m logn) time if the problem graph has n vertices and m edges. A modification for dense graphs gives a running time of 0(n 2 ). We also show that the unmodified algorithm runs in 0(n(log n) 2 +m) time on an average graph, assuming a uniform probability distribution.