Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/1933

 Title: A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs Authors: Markov, MinkoIonut Andreica, MugurelManev, KrassimirTapus, Nicolae Keywords: Algorithmic Graph TheoryLongest PathCactus 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. URI: http://hdl.handle.net/10525/1933 ISSN: 1312-6555 Appears in Collections: Volume 6 Number 3

Files in This Item:

File Description SizeFormat