A linear time algorithm for computing longest paths in cactus graphs

MaRDI QIDQ5747187zbMATH OpenFDO

Authors Minko Markov, Mugurel Ionuţ Andreica, Krassimir N. Manev, Nicolae Ţăpuş

Publication date 11 February 2014

Full work available at URL http://serdica-comp.math.bas.bg/index.php/serdicajcomputing/article/view/158/160

zbMATH Keywords

cactus graphslongest pathalgorithmic graph theory

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• Algorithms and Computation
• A linear time algorithm for computing longest paths in 2-trees.
• On computing longest paths in small graph classes
• scientific article; zbMATH DE number 2166874
• Computing and counting longest paths on circular-arc graphs in polynomial time

Cited in

(6)

• A linear time algorithm for computing longest paths in 2-trees.
• A modified optimal algorithm for 2-Maxian location problems on cactus graphs
• The 2-maxian problem on cactus graphs
• Broadcasting on cactus graphs
• A single exponential-time FPT algorithm for cactus contraction
• Integer programming approach to static monopolies in graphs

This page was built for publication: A linear time algorithm for computing longest paths in cactus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5747187)