Geodesic
A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
Serdica Journal of Computing, Tome 6 (2012) no. 3, pp. 287-298 Cet article a éte moissonné depuis la source Bulgarian Digital Mathematics Library

Voir la notice de l'article

We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes the label of each vertex from the labels of its children. The time complexity of our algorithm is linear in the number of vertices, thus improving the previously best quadratic time algorithm.
Keywords: Algorithmic Graph Theory, Longest Path, Cactus Graphs 
@article{SJC_2012_6_3_a2,
     author = {Markov, Minko and Ionut Andreica, Mugurel and Manev, Krassimir and Tapus, Nicolae},
     title = {A {Linear} {Time} {Algorithm} for {Computing} {Longest} {Paths} in {Cactus} {Graphs}},
     journal = {Serdica Journal of Computing},
     pages = {287--298},
     year = {2012},
     volume = {6},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2012_6_3_a2/}
}
TY  - JOUR
AU  - Markov, Minko
AU  - Ionut Andreica, Mugurel
AU  - Manev, Krassimir
AU  - Tapus, Nicolae
TI  - A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
JO  - Serdica Journal of Computing
PY  - 2012
SP  - 287
EP  - 298
VL  - 6
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SJC_2012_6_3_a2/
LA  - en
ID  - SJC_2012_6_3_a2
ER  - 
%0 Journal Article
%A Markov, Minko
%A Ionut Andreica, Mugurel
%A Manev, Krassimir
%A Tapus, Nicolae
%T A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
%J Serdica Journal of Computing
%D 2012
%P 287-298
%V 6
%N 3
%U http://geodesic.mathdoc.fr/item/SJC_2012_6_3_a2/
%G en
%F SJC_2012_6_3_a2
Markov, Minko; Ionut Andreica, Mugurel; Manev, Krassimir; Tapus, Nicolae. A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs. Serdica Journal of Computing, Tome 6 (2012) no. 3, pp. 287-298. http://geodesic.mathdoc.fr/item/SJC_2012_6_3_a2/