A polynomial time algorithm for longest paths in biconvex graphs

DOI10.1007/978-3-642-19094-0_20MaRDI QIDQ3078397zbMATH OpenOpenAlexFDO

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

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

dynamic programmingcomplexitypolynomial algorithmlongest path problembiconvex graphs

Mathematics Subject Classification ID

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

Recommendations

• The Longest Path Problem Is Polynomial on Interval Graphs
• The longest path problem has a polynomial solution on interval graphs
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• Algorithms for long paths in graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs

Cites work

• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Biconvex graphs: Ordering and algorithms
• Bipartite permutation graphs
• Graph Classes: A Survey
• Linear algorithm for optimal path cover problem on interval graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• On computing longest paths in small graph classes
• The Longest Path Problem Is Polynomial on Interval Graphs
• The longest path problem is polynomial on cocomparability graphs

Cited in

(5)

• scientific article; zbMATH DE number 682567 (Why is no real title available?)
• Linear structure of bipartite permutation graphs and the longest path problem
• The longest path problem in odd-sized \(O\)-shaped grid graphs
• Algorithms for long paths in graphs
• Longest-edge \(n\)-section algorithms: properties and open problems

This page was built for publication: A polynomial time algorithm for longest paths in biconvex graphs

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