A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, Minko; Ionut Andreica, Mugurel; Manev, Krassimir; Tapus, Nicolae

Serdica Journal of Computing (2012)

  • Volume: 6, Issue: 3, page 287-298
  • ISSN: 1312-6555

Abstract

top
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.

How to cite

top

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 -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.