William Evans ; Mohammad Ali Safari
-
Directed One-Trees
dmtcs:3429 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3429
Directed One-TreesArticle
Authors: William Evans 1; Mohammad Ali Safari 1
NULL##NULL
William Evans;Mohammad Ali Safari
1 Computer Science Department
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.
Boting Yang;Yi Cao, 2007, Standard directed search strategies and their applications, Journal of Combinatorial Optimization, 17, 4, pp. 378-399, 10.1007/s10878-007-9121-1.