An algorithm for constructing a k-tree for a k-connected matroid

Abstract

For a k-connected matroid M, Clark and Whittle showed there is a tree that displays, up to a natural equivalence, all non-trivial k-separations of M. In this paper, we present an algorithm for con- structing such a tree, and prove that, provided the rank of any subset of E(M) can be found in constant time, the algorithm runs in polynomial time in jE(M)j.