Geodesic
Minimum Eccentricity Shortest Paths in some Structured Graph Classes
Journal of graph algorithms and applications, Tome 20 (2016) no. 2, pp. 299-322 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

We investigate the Minimum Eccentricity Shortest Path problem in some structured graph classes. It asks for a given graph to find a shortest path with minimum eccentricity. Although it is NP-hard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distance-hereditary graphs (generalizing the previous result for trees) and give a generalised approach which allows to solve the problem in polynomial time for other graph classes. This includes chordal graphs, dually chordal graphs, graphs with bounded tree-length, and graphs with bounded hyperbolicity. Additionally, we give a simple algorithm to compute an additive approximation for graphs with bounded tree-length and graphs with bounded hyperbolicity. 
@article{JGAA_2016_20_2_a5,
     author = {Feodor Dragan and Arne Leitert},
     title = {Minimum {Eccentricity} {Shortest} {Paths} in some {Structured} {Graph} {Classes}},
     journal = {Journal of graph algorithms and applications},
     pages = {299--322},
     year = {2016},
     volume = {20},
     number = {2},
     doi = {10.7155/jgaa.00394},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00394/}
}
TY  - JOUR
AU  - Feodor Dragan
AU  - Arne Leitert
TI  - Minimum Eccentricity Shortest Paths in some Structured Graph Classes
JO  - Journal of graph algorithms and applications
PY  - 2016
SP  - 299
EP  - 322
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00394/
DO  - 10.7155/jgaa.00394
LA  - en
ID  - JGAA_2016_20_2_a5
ER  - 
%0 Journal Article
%A Feodor Dragan
%A Arne Leitert
%T Minimum Eccentricity Shortest Paths in some Structured Graph Classes
%J Journal of graph algorithms and applications
%D 2016
%P 299-322
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00394/
%R 10.7155/jgaa.00394
%G en
%F JGAA_2016_20_2_a5
Feodor Dragan; Arne Leitert. Minimum Eccentricity Shortest Paths in some Structured Graph Classes. Journal of graph algorithms and applications, Tome 20 (2016) no. 2, pp. 299-322. doi: 10.7155/jgaa.00394

Cité par Sources :