Geodesic
Finding Hamilton cycles in robustly expanding digraphs
Journal of graph algorithms and applications, Tome 16 (2012) no. 2, pp. 335-358 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

We provide an NC algorithm for finding Hamilton cycles in directed graphs with a certain robust expansion property. This property captures several known criteria for the existence of Hamilton cycles in terms of the degree sequence and thus we provide algorithmic proofs of (i) an `oriented' analogue of Dirac's theorem and (ii) an approximate version (for directed graphs) of Chvátal's theorem. Moreover, our main result is used as a tool in a recent paper by Kühn and Osthus, which shows that regular directed graphs of linear degree satisfying the above robust expansion property have a Hamilton decomposition, which in turn has applications to TSP tour domination. 
@article{JGAA_2012_16_2_a8,
     author = {Demetres Christofides and Peter Keevash and Daniela K\"uhn and Deryk Osthus},
     title = {Finding {Hamilton} cycles in robustly expanding digraphs},
     journal = {Journal of graph algorithms and applications},
     pages = {335--358},
     year = {2012},
     volume = {16},
     number = {2},
     doi = {10.7155/jgaa.00261},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00261/}
}
TY  - JOUR
AU  - Demetres Christofides
AU  - Peter Keevash
AU  - Daniela Kühn
AU  - Deryk Osthus
TI  - Finding Hamilton cycles in robustly expanding digraphs
JO  - Journal of graph algorithms and applications
PY  - 2012
SP  - 335
EP  - 358
VL  - 16
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00261/
DO  - 10.7155/jgaa.00261
LA  - en
ID  - JGAA_2012_16_2_a8
ER  - 
%0 Journal Article
%A Demetres Christofides
%A Peter Keevash
%A Daniela Kühn
%A Deryk Osthus
%T Finding Hamilton cycles in robustly expanding digraphs
%J Journal of graph algorithms and applications
%D 2012
%P 335-358
%V 16
%N 2
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00261/
%R 10.7155/jgaa.00261
%G en
%F JGAA_2012_16_2_a8
Demetres Christofides; Peter Keevash; Daniela Kühn; Deryk Osthus. Finding Hamilton cycles in robustly expanding digraphs. Journal of graph algorithms and applications, Tome 16 (2012) no. 2, pp. 335-358. doi: 10.7155/jgaa.00261

Cité par Sources :