A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs

DOI10.1007/978-3-642-19094-0_20zbMath1318.05080MaRDI QIDQ3078397

C. Pandu Rangan, N. S. Narayanaswamy, Esha Ghosh

Publication date: 20 February 2011

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_20

zbMATH Keywords

complexity; dynamic programming; polynomial algorithm; longest path problem; biconvex graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

90C39: Dynamic programming

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)