[hal-01184386] Directed One-Trees

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(n^2) recognition algorithm and an O(n^2) algorithm for solving the Hamiltonian cycle problem on directed one-trees.

from HAL : Dernières publications http://ift.tt/1UISdSD