Finding optimum branchings

Research output: Contribution to journalArticle

224 Scopus citations

Abstract

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
JournalNetworks
Volume7
Issue number1
DOIs
StatePublished - Jan 1 1977
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications

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

Cite this