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.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.67-72, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184386
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:38:58
Dernière modification le : jeudi 11 mai 2017 - 01:02:51
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:05:28

Fichier

dmAE0114.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184386, version 1

Collections

Citation

William Evans, Mohammad Ali Safari. Directed One-Trees. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.67-72, 2005, DMTCS Proceedings. 〈hal-01184386〉

Partager

Métriques

Consultations de la notice

320

Téléchargements de fichiers

106