A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, Minko, et al. "A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs." Serdica Journal of Computing 6.3 (2012): 287-298. <http://eudml.org/doc/219662>.

@article{Markov2012,
abstract = {ACM Computing Classification System (1998): G.2.2.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.The work performed by this author was partially funded by the Romanian National Council for Scientific Research (CNCS)-UEFISCDI under research grant PD\_240/2010 (AATOMMS – contract no. 33/28.07.2010), from the PN II – RU program, and by the Sectoral Operational Programme Human Resources Development 2007-2013 of the Romanian Ministry of Labour, Family and Social Protection through the financial agreement POSDRU/89/1.5/S/62557.},
author = {Markov, Minko, Ionut Andreica, Mugurel, Manev, Krassimir, Tapus, Nicolae},
journal = {Serdica Journal of Computing},
keywords = {Algorithmic Graph Theory; Longest Path; Cactus Graphs; algorithmic graph theory; longest path; cactus graphs},
language = {eng},
number = {3},
pages = {287-298},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs},
url = {http://eudml.org/doc/219662},
volume = {6},
year = {2012},
}

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
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 6
IS - 3
SP - 287
EP - 298
AB - ACM Computing Classification System (1998): G.2.2.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.The work performed by this author was partially funded by the Romanian National Council for Scientific Research (CNCS)-UEFISCDI under research grant PD_240/2010 (AATOMMS – contract no. 33/28.07.2010), from the PN II – RU program, and by the Sectoral Operational Programme Human Resources Development 2007-2013 of the Romanian Ministry of Labour, Family and Social Protection through the financial agreement POSDRU/89/1.5/S/62557.
LA - eng
KW - Algorithmic Graph Theory; Longest Path; Cactus Graphs; algorithmic graph theory; longest path; cactus graphs
UR - http://eudml.org/doc/219662
ER -