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

algorithmic graph theorycactus graphslongest path

Mathematics Subject Classification ID

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

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)

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