BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2012 >
Volume 6 Number 3 >

Please use this identifier to cite or link to this item:

Title: A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
Authors: Markov, Minko
Ionut Andreica, Mugurel
Manev, Krassimir
Tapus, Nicolae
Keywords: Algorithmic Graph Theory
Longest Path
Cactus Graphs
Issue Date: 2012
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 6, No 3, (2012), 287p-298p
Abstract: 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.
Description: ACM Computing Classification System (1998): G.2.2.
ISSN: 1312-6555
Appears in Collections:Volume 6 Number 3

Files in This Item:

File Description SizeFormat
sjc-vol6-num3-2012-p287-p298.pdf199.93 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License