# 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

## Access Full Article

top## Abstract

top## How to cite

topMarkov, 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 ?

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