Finding optimum branchings

Research output: Contribution to journalArticlepeer-review

276 Scopus citations


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(n2). 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.

Original languageEnglish (US)
Pages (from-to)25-35
Number of pages11
Issue number1
StatePublished - 1977
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Finding optimum branchings'. Together they form a unique fingerprint.

Cite this