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 language | English (US) |
---|---|
Pages (from-to) | 25-35 |
Number of pages | 11 |
Journal | Networks |
Volume | 7 |
Issue number | 1 |
DOIs | |
State | Published - 1977 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications