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-Trees
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.
Digraph searching, directed vertex separation and directed pathwidth
2 Documents citing this article
Source : OpenCitations
Yang, Boting; Cao, Yi, 2007, Standard Directed Search Strategies And Their Applications, Journal Of Combinatorial Optimization, 17, 4, pp. 378-399, 10.1007/s10878-007-9121-1.