Directed One-Trees
William Evans, Mohammad Ali Safari
Abstract
We identify the class of directed one-trees and prove the so-called min-max theorem for them. As a consequence, we establish the equality of directed tree-width and a new measure, d-width, on this class of graphs. In addition, we prove a property of all directed one-trees and use this property to create an O(n2) recognition algorithm and an O(n2) algorithm for solving the Hamiltonian cycle problem on directed one-trees.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page