A polynomial time algorithm for longest paths in biconvex graphs
DOI10.1007/978-3-642-19094-0_20zbMATH Open1318.05080OpenAlexW1539367839MaRDI QIDQ3078397FDOQ3078397
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
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
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)
Cites Work
- Graph Classes: A Survey
- Algorithmic graph theory and perfect graphs
- On computing longest paths in small graph classes
- The Longest Path Problem Is Polynomial on Interval Graphs
- Algorithms and Computation
- Linear algorithm for optimal path cover problem on interval graphs
- Bipartite permutation graphs
- Biconvex graphs: Ordering and algorithms
- Linear structure of bipartite permutation graphs and the longest path problem
- The longest path problem is polynomial on cocomparability graphs
Cited In (5)
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)
