DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional