Geodesic
Directed One-Trees
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a38,
     author = {Evans, William and Safari, Mohammad Ali},
     title = {Directed {One-Trees}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3429},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3429/}
}
TY  - JOUR
AU  - Evans, William
AU  - Safari, Mohammad Ali
TI  - Directed One-Trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3429/
DO  - 10.46298/dmtcs.3429
LA  - en
ID  - DMTCS_2005_special_250_a38
ER  - 
%0 Journal Article
%A Evans, William
%A Safari, Mohammad Ali
%T Directed One-Trees
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3429/
%R 10.46298/dmtcs.3429
%G en
%F DMTCS_2005_special_250_a38
Evans, William; Safari, Mohammad Ali. Directed One-Trees. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3429. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3429/

Cité par Sources :