A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs

DOI10.1016/0020-0190(89)90044-6zbMath0688.68032OpenAlexW2059355023MaRDI QIDQ1263968

Manrique Mata, Gary MacGillivray, John A. Ellis

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90044-6

zbMATH Keywords

NP-completelongest path outerplanar graph algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

Approximating the pathwidth of outerplanar graphs ⋮ A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs ⋮ A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs ⋮ Partial and perfect path covers of cographs

Cites Work

• A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs
• Parallel concepts in graph theory
• Linear-time computability of combinatorial problems on series-parallel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs