A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs

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

N. S. Narayanaswamy, C. Pandu Rangan, 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

complexitydynamic programmingpolynomial algorithmlongest path problembiconvex graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Dynamic programming (90C39) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Linear algorithm for optimal path cover problem on interval graphs
• Bipartite permutation graphs
• Biconvex graphs: Ordering and algorithms
• Algorithmic graph theory and perfect graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• The Longest Path Problem is Polynomial on Cocomparability Graphs
• ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
• The Longest Path Problem Is Polynomial on Interval Graphs
• Graph Classes: A Survey
• Algorithms and Computation

This page was built for publication: A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs