Loading [MathJax]/jax/output/HTML-CSS/jax.js

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-TreesConference paper

Authors: William Evans 1; Mohammad Ali Safari 1

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


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: tree-width,tree-decomposition,d-width,d-decomposition,haven order,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

2 Documents citing this article

Consultation statistics

This page has been seen 219 times.
This article's PDF has been downloaded 206 times.