Skip to Main content Skip to Navigation
Conference papers

Directed One-Trees

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

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184386
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:58 AM
Last modification on : Friday, December 18, 2020 - 5:30:03 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:05:28 AM

File

dmAE0114.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184386, version 1

Collections

Citation

William Evans, Mohammad Ali Safari. Directed One-Trees. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.67-72. ⟨hal-01184386⟩

Share

Metrics

Record views

646

Files downloads

610